Great Algorithms that Revolutionized Computing

[avmich]

Hash tables were highly praised by Knuth as "the invention of the year". If we have binary search in the list, we should have hashes.

[gamegoblin]

This is a pretty bad list. To say that the fast inverse square root trick revolutionized computing is a joke. I doubt anyone on HN was unaware of any of these algorithms and couldn't name more "revolutionary" ones.

No FFT? No simplex algorithm? Hashing? Strassen's?

[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.

[cliveowen]

I can't fathom why the Simplex algorithm wasn't included, it's considered, with reason, the most important algorithm of the 19th century.

[gamegoblin]

Nitpick - Simplex is 20th century.

A cool 19th century algorithm is Radix Sort, though.

[TTPrograms]

...FFT?

[btilly]

The Fast Fourier Transform absolutely deserves to be on the list.

All of signal processing went from, "We'd like to do a Fourier Transform but can't afford O(n^2) so here is a faster alternative that kind of does something useful" to, "We start with a FFT."

[tlarkworthy]

yeah, bit biased towards CS.

Neural nets opened a lot of doors.

Bellman equation is in a lot of equipment.

[fla]

And Reed-Solomon error correction.

[mjcohen]

Which seems to have been invented by Gauss.

[bbosh]

I'm not sure you can call the Euclidean algorithm a "computer algorithm", it having been discovered some 2,000 years before computers existed.

[carlosvega]

What about RSA?

[TrainedMonkey]

Seems to be covered by public key cryptography.

[michaelochurch]

Let me add: Least Angle Regression.

It's an efficient way for performing Lasso (L^1-penalization) to regression models, which has the benefit of (in addition to reducing risk of overfitting) producing sparse models.

[GFK_of_xmaspast]

That's a little specific.

SIAM put out a 'ten algorithms of the century' https://www.siam.org/pdf/news/637.pdf a few years ago and it's really tough to argue with six or seven or eight of them.

(MCMC, simplex, Krylov, Householder decomposition, QR, Quicksort, FFT, Ferguson&Forcade's integer relation stuff (that led to stuff like PSLQ), and fast multipole)

And FORTRAN.