Re:Ask HN: What's the most interesting algorithm?
by mroll on Saturday May 07, 2016 @04:59PM
(#11651323)
I like the fast fourier transform method for fast integer multiplication. Only applicable on really big inputs, but the idea is that it computes the fft of both integers, does point-wise multiplication of the resulting vectors, then does the inverse fft to recover the product. More about this (https://en.wikipedia.org/wiki/Multiplication_algorithm#Fouri...).
Another interesting but asymptotically slower integer/polynomial multiplication algorithm is Karatsuba's.
Another interesting but asymptotically slower integer/polynomial multiplication algorithm is Karatsuba's.