3 ms·

Speaking of incredibly cool algorithms based on Fourier transforms, the Schoenage-Strassen algorithm for multiplying integers is also amazing: http://en.wikipe

Speaking of incredibly cool algorithms based on Fourier transforms, the Schoenage-Strassen algorithm for multiplying integers is also amazing: http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen... At least to me, it seems hard to imagine that multiplying two N-bit integers could be done with less than O(N^2) operations. Schoenage-Strassen lets you do it using O(N log N log log N) operations!

lmkg 16y ago
This is the one that blew my mind. "If we treat the numbers as polynomials, then the multiplication can be reduced to a Fourier transform!" is also one of those things that sounds like a punchline. Each step of the algorithm just sounds stupider and stupider, and slower and slower... and then you get to the last step, where all the multiplications by exponentials of complex numbers get replaced by bitshifts. Suddenly the entire algorithm collapses in on itself to reveal something efficient.