4 ms·
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
by cperciva 16y ago
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.
- jules 16y agoLink?
- cperciva 16y agohttp://www.daemonology.net/papers/thesis.pdf http://www.daemonology.net/papers/thesis.pdf
- michael_nielsen 16y agoSpeaking 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 agoThis 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.