What are the most amazing algorithms?

Question

What are the most amazing algorithms you know. Not boring stuff like sorting.

mikewarot · Accepted Answer

Direct Digital Synthesis[1] - it is almost trivial... you just accumulate phase with an adder that is much longer than the output resolution, you take the top bits and feed them into a sine lookup, and you can generate a sine wave of arbitrary frequency and phase.
The amazing part is that it is common to have resolution of 1/100 of a Hertz on RF signals. Correcting frequency to lock to WWV is trivial bit of math.
Long ago, I had a 68HC11 processor with 512 bytes of EEPROM to store my program into, part of it was locking on to the speed of a production line, with a pulse that happened about every 15 inches (one revolution of the drive wheel) and adjusting timing in a simulated phase locked loop to get 1/10" counts. I had an DDS in there along with all the other code and it worked great. That part of it was about 50 bytes, if I recall correctly.
[1] https://en.wikipedia.org/wiki/Direct_digital_synthesis

wnkrshm · Answer

Monte Carlo integration and its many many offshoot techniques (biased and unbiased) are still fascinating to me.It's less impressive if you simply see the result, e.g. in ray traced images but what is done mathematically, is evaluate an expression of infinitely-nested luminance integrals.

cushpush · Answer

There's a youtube channel called Two Minute Papers, my latest favorite algorithms have to do with fluid simulation and generative near-fit images for beaches that don't exist. I'm not sure what your question is, protein folding is pretty amazing. So is XOR.

ulrischa · Answer

Kriging interpolation

Vervious · Answer

Sorting algorithms are pretty amazing, though.

rvz · Answer

Zstandard. [0][0] http://facebook.github.io/zstd

What are the most amazing algorithms?

What are the most amazing algorithms you know. Not boring stuff like sorting.

Monte Carlo integration and its many many offshoot techniques (biased and unbiased) are still fascinating to me.
It's less impressive if you simply see the result, e.g. in ray traced images but what is done mathematically, is evaluate an expression of infinitely-nested luminance integrals.

There's a youtube channel called Two Minute Papers, my latest favorite algorithms have to do with fluid simulation and generative near-fit images for beaches that don't exist. I'm not sure what your question is, protein folding is pretty amazing. So is XOR.

Kriging interpolation

Sorting algorithms are pretty amazing, though.

Zstandard. [0]
[0] http://facebook.github.io/zstd