[rumbler]

That inverse square root algorithm is a neat trick, but it did not revolutionize anything.

In addition to several algorithms already mentioned, I feel that suffix trees and suffix array algorithms should be there as well. They are making all kinds of approximate searches feasible in bioinformatics.

[mistercow]

I'm also not sure isqrt counts as a new algorithm. It's just Newton's method with a bit hack to exploit the floating point format and extract a good starting point.