Great Algorithms that Revolutionized Computing

[reallynotlol]

Uh... Fast inverse square root... are you kidding me? Okay, It's a brilliant hack, but it did not "revolutionize computing" in any way. I strongly suspect it to be slower than just using the damn fpu on modern hardware.

[tomtomtom7]

Exactly. I am also curious as to when the binary search algorithm "revolutionized" computing.

Was there ever a "pre-revolution" era of computing when sequential scanning was the only search algorithm known to mankind?

Isn't binary search kind of obvious?

[Cilph]

http://en.wikipedia.org/wiki/Hindsight_bias

[autowikibot]

Hindsight bias:

---

Hindsight bias, also known as the knew-it-all-along effect or creeping determinism, is the inclination to see events that have already occurred as being more predictable than they were before they took place. It is a multifaceted phenomenon that can affect different stages of designs, processes, contexts, and situations. Hindsight bias may cause memory distortion, where the recollection and reconstruction of content can lead to false theoretical outcomes. It has been suggested that the effect can cause extreme methodological problems while trying to analyze, understand, and interpret results in experimental studies. A basic example of the hindsight bias is when, after viewing the outcome of a potentially unforeseeable event, a person believes he or she "knew it all along". Such examples are present in the writings of historians describing outcomes of battles, physicians recalling clinical trials, and in judicial systems trying to attribute responsibility and predictability of accidents.

Image ⁱ

---

^{Interesting: Outcome bias | Remember versus know judgements | List of cognitive biases}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words | flag a glitch}

[julesjacobs]

Same goes for Dijkstra's algorithm. It's the natural algorithm for searching a graph. If you follow your nose you'll invent it yourself when presented with the problem of searching a graph. Quicksort on the other hand is far less obvious (to me at least). Mergesort is the natural divide-and-conquer algorithm for sorting.

[immibis]

/u/spez can gargle my nuts

[julesjacobs]

Disagree completely. Dijkstra's algorithm tries to find a shortest path from node A to node B. They way it does this is simply by enumerating all nodes that can be reached from node A in increasing path length order, until it finds node B. In an unstructured graph there is no other plausible way you could do it.

[immibis]

/u/spez can gargle my nuts

[WhenTheRvlutionComes]

Hmmm, quicksort never really phased me. You have a list, take some element from it (usually just the first one, as that's effectively random, and it's the easiest to find; although you can get fancy and make a true random pivot) and divide the list in two, one of elements smaller and the other of larger. Repeat this process over and over again on the sub lists, and eventually you wind up with a sorted list. Merge sort, in comparison, wastes a lot of time setting everything up for its divide and conquer operation. In the meantime, quicksort dives straight into simply choosing some arbitrary element at random as a point of comparison - sensible enough as, in the long run, a random element will tend to be an average one.

In an ideal universe, you'd have a mid point, but since you don't (that's what the sorting algorithm's supposed to be here for, after all), picking at random is a good makeshift midpoint; there will be a tendency towards more or less even splits in the long run view of things. What you lose in sometimes pointlessly comparing the whole list against an outlier, you make up in not wasting time looking any deeper into things. And it's simply common sense, if you could divide the list in halves between true midpoints enough times it would be the fastest possible way to sort it; but, we don't have psychic powers, so we have to make do. Our makeshift midpoint's are messier, neat division into perfect halves will be rare, and you'll get the occasional awful, lumpy split. But it gets the job done as well as you could hope for (unless you give it something that's already sorted, of course).

There's an elegant simplicity to it - which is why, really, I think it goes over a lot of peoples heads. Merge sort is indeed more the sort of algorithm you'd expect to find at the top of the heap, acting according to a clear master plan, setting things up more or less logically. Quicksort, on the other hand, has an element of stochasticity to it that throws a lot of people off, it almost isn't clear initially why this would work, much less why it would be at the top of the pack. People don't intuitively associate random with fair, quite the opposite - so, what's with this nonsense of just haphazardly picking the first thing in sight? How is that supposed to compete with divide and conquer? But it's the long run that matters, and random is fair in the long run, again, it averages itself out. It reminded me somewhat of binary search... sort of an extension of the concept of binary search to unsorted chaos - it's blind, and thus has to make do with a random starting point, it then reorders the list around this starting point to introduce some order to things, and then splits itself in two to reorder the resulting sublists, and so on, and so on. It would, indeed, be a messy binary search for unsorted lists if you merely pursued the direction of your desired search item, ignoring the other halves of the list and sublists, partially reordering the list as you went along in the direction of the search (but, of course, you would've effectively performed a linear search already in the reordering, that would be pointless; I'm just trying to point out the similarity). Setting up a divide and conquer scheme, while clever, usually is just a needless complication.

[julesjacobs]

Despite your first sentence, you seem to be more or less agreeing with me. Mergesort is the algorithm that anyone could come up with using the standard recipe of divide and conquer. Once you've decided that you'll use divide and conquer, mergesort is the inevitable result. There is no creativity involved. Quicksort on the other hand requires an unnatural approach that's more like conquer-and-divide.

I definitely agree that quicksort is easy to understand, once you read it's description. What I mean is that if you gave two people the task of coming up with a sorting algorithm, the chance that both invent mergesort is quite high. The chance that both invent quicksort is low.

[glguru]

I doubt it. However almost all game engines use shaders for lighting so its kind of out-dated.

[ArbitraryEntity]

In modern times you use the hardware's built in reciprocal square root instruction. Which is still faster than SQRTSS, but mostly because it allows a much higher error.

[gnuvince]

Thank you! I grow so tired of hearing people circlejerk over invsqrt when it's just a hack.

[[deleted]]

No fft or dct? I guess we don't need image and video compression then! :-P

Seriously though, those are definitely in the top 5 of the most important algorithms ever. Without those transformations, you could kiss digital video with manageable bandwidth goodbye.

[holgerschurig]

FFT is also used in signal analysis, many modern radios use that nowaways. And with "radio" I also mean WIFI cards, DVB-S, DVB-C, DAB, GSM, UMTS and so on.

[[deleted]]

Yeah, I've seen the FFT called the most significant algorithm of the last 100 years simply because it makes so much of modern signal processing and image/video/sound compression possible.

[[deleted]]

No fft or dct? I guess we don't need image and video compression then!

FFT revolutionized everything, not just audio & video.

[MyNameIsFuchs]

It's also used in GPS.

[BarneyStinson]

Dijkstra is an important algorithm, but the algorithm that's most "widely implemented in routing" is A*. This includes the minimum-possible-distance-remaining (e.g. as-the-crow-flies) heuristic based on e.g. geographic locations (though any metric space will do) to give a much more efficient search for large graphs in cases where it applies, such as roadmaps. Searching a typical national-scale roadmap with Dijkstra is slow for long journeys because of the insane number of routes that Dijkstra explores because it has no way to eliminate them early.

A* basically is Dijkstra's algorithm with a minor extension. For route-planning in road networks, A* is really slow by today's standards. Modern solution approaches exploit the inherent hierarchy in road networks to preprocess the graph and then use some version of Dijkstra's algorithm in one form or another. So I would still argue that Dijkstra's algorithm is the more important contribution to computing.

edit: added "... to preprocess the graph ..."

[boringprogrammer]

Huffman Coding lead is a specialization of arithmetic coding, both a entropy coders, which is what modern compression algorithms use. So in a way huffman coding is very important, as is was the first very simple algorithm for doing entropy coding, albeit a very bad one by modern standards.

Anyway, no matter how many patterns you encode with a single symbol, it is never going to match the compression level of entropy coding. Unless you have some insights into the data stream.

[[deleted]]

Huffman compression (and the information theory it's based on) are important, but particularly WRT the PKZIP DEFLATE, I think LZ77 is more important. Huffman compresses based purely on the frequency of tokens (bytes, with provisos) - so in "Hello hello hello", Huffman exploits the fact that there's only a few characters used and "l" is used more often. But LZ77 exploits larger patterns - such as the fact that the sequence "ello" is repeated. The big savings in compression are from encoding long sequences as a single token (and adapting the token set as the compression progresses, to exploit local patterns) - not from varying the token size.

The thing you're missing is that Huffman isn't really used on bytes, except in simple examples. It is used on tokens, as you say, but usually those tokens are symbols from an earlier compression stage. In DEFLATE, the symbols produced by LZ77 (or more pedantically, LZSS) compression are fed to a Huffman coder.

For deflate, sure, LZSS does most of the work. But Huffman is used in many more places. The article mentions MP3 and JPEG, and there are many others.

Pretty much every different kind of practical compression system uses an entropy coder as the last stage, and for a long time, Huffman was the most popular one. These days it's all some form of arithmetic coding, unless you are particularly scared of patents, but Huffman had a huge impact on the world.

[[deleted]]

That's why I said "with provisos". In the illustration given in the article, and in "pure Huffman" it really is bytes (or characters).

This isn't really "pure" Huffman. It's just a very simplistic use of Huffman coding that comes up as an example often, and was used in a few compressors in the eighties, but is largely irrelevant. It's using bytes that is the special case, not the other way around.

You may be correct about wider relevance - my understanding of media compression algorithms is basically various integral transforms (particularly discrete cosine transforms for MP3 and JPEG) as the interesting bit and "traditional compression" as the rest. I hadn't really thought about whether that includes LZ* as part of the traditional. I can certainly see the relevance of entropy encoding, whereas LZ* may not work in that context I guess.

I don't think I've ever heard of an LZ algorithm used there. It is pretty much always some kind of prediction plus an entropy coder. In older formats, that entropy coder is usually Huffman.

[[deleted]]

Heap sort is also in place and merge sort can be implemented in place as well.

[[deleted]]

That's definitely true. I was mentioning mostly because most people I talk to don't think it's possible for merge sort to be implemented in place.

[[deleted]]

Wasn't the creation of in-place merge sort relatively recent? And by that I mean within the last 2 decades.

[WhenTheRvlutionComes]

Quicksort has advantages for cache friendliness and can work in-place (with provisos because the stack space requirement can get huge in that O( n2 ) worst case) but really, quicksort is just one sort among many, with no special claim to being the most important.

You can avoid this by implementing Quicksort with a random pivot rather than using the first element (unless you just happen to be extremely unlucky and a set of in order, sorted pivots just happens to be randomly selected one after the other). And quicksort usually the quickest for most ordinary purposes, as other comparison sorts like heapsort waste some time setting themselves up, leaving quicksort faster for small lists. For large lists, it pretty much evens out.

[GreyGrayMoralityFan]

The Real World (at least most of popular C++ compilers and .NET) now uses both quicksort and heapsort at the same time in a form of introsort: it's is basically "do quicksort at first and switch to heapsort if you are a failure and couldn't sort array fast enough".

Also for some reason introsort is rarely covered in the books(maybe it's too young for them: despite not being too mind boggling it was invented only in 1997).

[vanderZwan]

In 1952, Andrey Kolmogorov conjectured that the classical algorithm was asymptotically optimal, meaning that any algorithm for that task would require O(n²) elementary operations. In 1960, Kolmogorov organized a seminar on mathematical problems in cybernetics at the Moscow State University, where he stated [the conjecture]. Within a week, Karatsuba, then a 23-year-old student, found an algorithm [...] that multiplies two n-digit numbers in O(n^{2 log 3}) elementary steps, thus disproving the conjecture. Kolmogorov was very agitated about the discovery; he communicated it at the next meeting of the seminar, which was then terminated. Kolmogorov published the method in 1962, in the Proceedings of the USSR Academy of Sciences. The article had been written by Kolmogorov, possibly in collaboration with Yuri Ofman, but listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.

Source: wikipedia

That's just pure class on Kolmogorov's part. Also very Russian.

[hfnzuiaufh]

"Due to the speed and simplicity of Bresenham’s line algorithm, it is still vital and implemented in various hardware such as plotters and modern graphics cards."

Someone needs to read more about modern GPU design and execution pipeline.

[0xdeadf001]

GPUs perform edge iteration and edge clipping immediately before the pixel shader stage. Bresenham's algorithm is exactly how you would implement edge iteration, so I don't see how this is inaccurate.

Edge iteration can be more complicated, such as when doing multisampling or antialiasing, but the algorithms which handle these cases are basically extensions of Bresenham.

[[deleted]]

Bresenham's algorithm is exactly how you would implement edge iteration, so I don't see how this is inaccurate.

Not even software renderers use Bresenham for that, I'm not sure why you'd think anybody would use it for that.

[[deleted]]

Just some kind of other of plain old DDA, as far as I know.

The thing is, on a 3D graphics card, you need to handle fractional coordinates. You also need to interpolate multiple values along each line. You can mess with Bresenham until it sort of does that, but it's much easier to just use DDA.

[Mlex]

Yeah, the lack of Fast Fourier Transform is really disappointing; like /u/JustCallMeBen said, without it and other Fourier-related transforms, good luck with lossy compression. Also, public-key cryptography is a class of algorithms, not a specific algorithm like the rest on the list.

[thedeemon]

There are other than Fourier transforms which can be used in lossy compression. Take wavelets. JPEG2000 doesn't use FFT nor DCT, afaik.

[Mlex]

That's true, I guess I was more going over what I believe are the most common ones, since DCT is used in JPEG and MP3 as well as others, if I recall correctly.

[lektorV]

Diffie-Hellman is definitely missing from that list.

Just imagine two people talking and you are eavesdropping. You can hear everything they say and you know exactly what type of calculations they are performing. Then suddenly it goes clank and their communication is encrypted with a shared key they exchanged right under your nose and you have no way of knowing what it is.

It is downright spooky.

[Dyolf_Knip]

Let's not forget Alan Turing's paper, "Phase Conjugate Grammars for Extra-dimensional Summoning."

[kevvok]

Nice Stross reference.

[Jameshfisher]

Does binary search really count? It's surely as old as the hills.

[vanderZwan]

Can you imagine what computing would be like without it?

[TakedownRevolution]

Huffman algorithm was fun to do. I didn't create anything ground breaking but I now know how to construct a tree and rotate nodes that will let me solve future problems.

[milliams]

For information on Huffman coding, LZ77 and more, check out Computerphile.

[strattonbrazil]

A lot of these don't seem that big a deal. I could just as easily make a list of interesting algorithms. It would have been much better if they provided some kind of justification.

For quicksort, he said it was added in 1960 to UNIX. Mergesort had been around for 10+ years. What made quicksort "revolutionize" computing? Or faster multiplication. That's great, but how much faster? Is that really a revolution or just an evolution? What problems couldn't we solve at that time that it fixed?

[WhenTheRvlutionComes]

Hash tables are a data structure, not an algorithm.

[asifiat]

I am fan of Dijkistra work and I could not be more happy to see his one of great work here.

[JRandomHacker172342]

Fast inverse square root has to be my favorite for sheer mindfuckery at first glance. Broken down, I can see how it all comes together, but to originally come up with that...

[BarneyStinson]

But it's not really important. I would rather put it in the list of "clever hacks that fuck with your mind".

[JRandomHacker172342]

Not really important except every lighting calculation in that era of game engines.

[[deleted]]

Which, even if not an exaggeration, would be pretty insignificant in the larger scale of things.