News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.