News for hackers. Stuff that matters.
Re:What algorithm blows your mind? (Reddit compsci) by cperciva on Tuesday October 26, 2010 @09:32AM (#1834080)
My mind is blown by the algorithm for matching with mismatches which I present in the first chapter of my thesis. It shouldn't be, given that I discovered this algorithm -- but somehow "I take the Fourier Transfer of the FreeBSD kernel" sounds more like the punch line to a joke than the first step in an algorithm.
Re:What algorithm blows your mind? (Reddit compsci) by michael_nielsen on Tuesday October 26, 2010 @09:37AM (#1834093)
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...

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!

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.
Re:What algorithm blows your mind? (Reddit compsci) by jules on Tuesday October 26, 2010 @10:29AM (#1834297)
Link?
Re:What algorithm blows your mind? (Reddit compsci) by cperciva on Tuesday October 26, 2010 @10:55AM (#1834428)