News for hackers. Stuff that matters.
Re:What algorithm blows your mind? (Reddit compsci) by lmkg on Tuesday October 26, 2010 @12:58PM (#1834986)
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.

There are no comments on this comment yet.