5 ms·

Ask HN: What are the most amazing algorithms?

8 points by ulrischa 3y ago

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

Vervious 3y ago
Sorting algorithms are pretty amazing, though.
- cushpush 3y ago
  merge sort is like how lee sedol beat Google's DeepGo that one game, in reverse.
wnkrshm 3y ago
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.
- ulrischa 3y ago
  Yes Monte Carlo is cool
cushpush 3y ago
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 3y ago
Kriging interpolation
rvz 3y ago
Zstandard. [0] [0] http://facebook.github.io/zstd http://facebook.github.io/zstd
mikewarot 3y ago
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 https://en.wikipedia.org/wiki/Direct_digital_synthesis
- tuckerpo 3y ago
  DDS is really nifty. Can have arbitrary, variable reference clocks for high speed ADCs as a use-case.

8 points by ulrischa 3y ago

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

Vervious 3y ago

Sorting algorithms are pretty amazing, though.

cushpush 3y ago
merge sort is like how lee sedol beat Google's DeepGo that one game, in reverse.

wnkrshm 3y ago

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.

ulrischa 3y ago
Yes Monte Carlo is cool

cushpush 3y ago

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 3y ago

Kriging interpolation

rvz 3y ago

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

mikewarot 3y ago

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 https://en.wikipedia.org/wiki/Direct_digital_synthesis

tuckerpo 3y ago
DDS is really nifty. Can have arbitrary, variable reference clocks for high speed ADCs as a use-case.