Skip

Which algorithms changed the world?
August 10, 2014 2:50 PM   Subscribe

A recent post to the blue proposed a set of equations that changed the word. As a computer professional, I'm curious, which algorithms transformed the world?

I'm not necessarily looking for 'algorithms a computer programmer should know' or 'algorithms we should teach in CS 101.' An algorithm impact on the world should be the primary criteria, rather than pracitioner familiarity or pedagogical use.
posted by pwnguin to Science & Nature (23 answers total) 60 users marked this as a favorite
 


With no better criteria than what immediately comes to mind:
  • Either arithmetic or Huffman encoding for data compression. I think you could make an argument for Lempel–Ziv here too, but Huffman & arithmetic encoding both start to think about data as something other than fixed length.
  • Public key encryption. Because holy crap.
  • Map-Reduce. Because thinking about big data sets changed.
  • Ray tracing. Because it pushed all sorts of thinking about "how can you get this result, but efficiently". I would suggest that from turning this on its head we get things like Warnock's algorithm, REYES, the raycasting renderers of the '90s, and from exploring it we get implicit surfaces and more. Related: Stochastic sampling in graphics.
  • Bezier curves, Bresenham's line algorithm, and I'm probably short-changing a bunch of other graphics primitives ideas. For similar reasons.
  • B-Trees.

posted by straw at 3:09 PM on August 10 [3 favorites]


The Viterbi algorithm.
posted by equalpants at 3:15 PM on August 10


A fast inverse square root function has been the subject of a lot of discussion, and it has contributed to the creation of realistic 3D environments.
posted by SpacemanStix at 3:15 PM on August 10


PageRank revolutionized searchability, and ultimately made the Worldwide Web's explosive growth usable.
posted by jackbishop at 3:19 PM on August 10 [2 favorites]






Forward Error Correction (AKA "Hamming Code")
posted by Chocolate Pickle at 4:06 PM on August 10 [2 favorites]


Also, time sharing about 50 years ago.

And symmetric multiprocessing about 20 years ago.
posted by Chocolate Pickle at 4:10 PM on August 10


The Genetic algorithm. This is used to solve all kinds of optimization problems which can't be solved any other way in practical time. Genetic algorthms don't necessarily find the best answer but they nearly always find almost the best answer, in hours or days instead of in millions of years.
posted by Chocolate Pickle at 4:14 PM on August 10 [2 favorites]


Quicksort.
Discrete Cosine Transform (aka, JPEG encoding).
posted by plinth at 4:36 PM on August 10


Simplex algorithm for solving linear programs.
posted by SemiSalt at 4:41 PM on August 10 [1 favorite]


Internet routing algorithm?

TCP algorithm for reliable communication over an unreliable channel?
posted by rustcrumb at 5:26 PM on August 10


Carrier sense multiple access with collision detection, aka Ethernet.

IP forwarding algorithm, the Internet Protocol


These two are why you can just plug one more machine into a computer network, and it all works without having to reconfigure everything else on the network. [This probably doesn't seem so amazing if you never had to set up a network in the 1990s.]
posted by benito.strauss at 6:39 PM on August 10


Diffie-Helleman key exchange. Transmitting secure information over an insecure channel. Flat out genius.
posted by It's Never Lurgi at 6:39 PM on August 10 [2 favorites]


Embarassingly, that title belongs to Ralph Merkle, although Diffie and Helleman devised the first practical algorithm. It amazes me that anyone was crazy enough to come up with something so obviously impossible.
posted by It's Never Lurgi at 7:13 PM on August 10 [1 favorite]


Ulam's Montecarlo method, for sure. Especially as he came up with it when recuperating from meningitis and wasn't supposed to be thinking very hard, so played a lot of solitaire and got wondering about the probabilities of winning …
posted by scruss at 7:26 PM on August 10


FFT.

The Fast Fourier Transform made the nuclear test ban treaty possible. Without it, computers could not process seismic data fast enough to determine (a) whether a particular set of tremors was a nuclear bomb or not and (b) where the tremors originated.
posted by pmb at 8:14 PM on August 10 [3 favorites]


The Smith-Waterman algorithm for sequence alignment has had an enormous impact on biomedical research (think human genome project and everything spawned from it).
posted by chrisamiller at 10:31 PM on August 10


The perceptron algorithm -- gave rise to neural networks, SVMs, and the general industry of supervised classification that drives most of AI and data analysis today.

Algorithms to do linear regression gave rise to the quantitative social and biomedical sciences.
posted by redlines at 5:24 AM on August 11


Ada Lovelace's "Note G" algorithm for generating Bernoulli numbers. It is arguably the very first computer program.
posted by kyrademon at 8:48 AM on August 11 [1 favorite]


The least squares method for finding a line that fits a set of data points (discovered by Gauss). It was originally used to determine the path of comets and asteroids.
posted by A dead Quaker at 5:04 AM on August 19


Kalman Filtering, which led to GPS and most modern guidance systems (from satellites to missiles, and I strongly suspect Google's car uses it), and has an absolutely eery ability to strip noise from signal at jaw-dropping rates.
posted by IAmBroom at 8:47 AM on November 2


« Older We just moved to northern Berg...   |  I'm in search of a grid it sty... Newer »

You are not logged in, either login or create an account to post comments



Post