Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: What's your favorite elegant/beautiful algorithm?

news.ycombinator.com

Post reply on HN
Print view View original

501–507 of 507 posts

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#501

Post by cben »

vanderZwan wrote: post #245
TomasHubelbauer wrote: post #103

I've always appreciated the Bresenham's line algorithm. It's a very simple algorithm and has been "superseded" by Xiaolin Wu's line which can also do antialiasing, but ever since I learnt about it, I've been very fond of it. Also the fact that it's an algorithm for use in computer graphics helps, because for me it's very easy to get excited about visual stuff as opposed to the more abstract CS stuff, which I have dee…

> It's a very simple algorithm and has been "superseded" by Xiaolin Wu's line which can also do antialiasing Actually, not really! Bresenham's Line Algorithm secretly has a very useful generic low-level algorithm at its core. It just happened to be created for drawing lines first. The thing most people miss is that it describes a way to do error-free repeated addition of a fraction using only integers and addition .…

Yep; it's one-dimentional variant of Error Diffusion (which itself is a notably beautiful dithering algorithm), where "input" = slope of line and output is quantized dy=0 or dy=1.

Dithering also appears in audio. The old PC Speaker had merely 1/0 states. It's supposed to be limited to square waves, limited and unpleasant, right? But at some point people figured out if you flip 1/0 fast enough you can approximate continuous values: http://bespin.org/~qz/pc-gpe/speaker.txt

I once played with using "error diffusion" like dithering to play wav files. In theory that should produce better audio than the simple fixed-table and PWM dithering suggesting in above article, but I did this on a much newer computer (Pentium?) by which time PC Speaker was irrelevant (only for hack value) and only reached 30-40 bits per input sample at 100% CPU. Plus as that article explains, simple PWM might(?) actually produce less noise from timing irregularity.

But the technique is not merely an obsolete hack! Every CD player that visibly brags it has "1-bit DAC" uses a closely related technique, though in fast hardware. See: https://en.wikipedia.org/wiki/Delta_modulation https://en.wikipedia.org/wiki/Delta-sigma_modulation Take me with a grain of salt, I always get confused trying to grok these... Full explanations of the noise shaping properties that make Delta-Sigma highly useful involve quite a bit of signal-processing, but the core accumulate-compare loop is a very simple algorithm...

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#502

Post by cben »

btilly wrote: post #405

The rsync algorithm. There is a theorem that it is impossible in general to remotely compare two files with less network traffic than it requires to simply send one file over the wire. But rsync does it. How? By accepting a theoretical but unlikely possibility of coming up with the wrong answer. What rsync does is compare hashes of ranges of stuff. If the hash comes out the same, the two are assumed to be identical w…

rsync was indeed a dramatic "this should not be possible" feat. But the way it uses rolling hashes is not the simplest possible. One side sends hashes of fixed-size chunks, the other scans input for rolling hash matches, which only works for 2 sides and requires non-cachable CPU work on at least one side.

There is an even simpler idea at the core of many modern backup programs (eg. bup, attic, borg)! Possibly pioneered in `gzip --rsyncable`, not sure. https://en.wikipedia.org/wiki/Rolling_hash#Content-based_sli... Each side slices files into chunks at points where rolling hash % N == 0, giving chunks of variable size averaging N. These points usually self-synchronize after insertions and deletions. This allows not just comparing 2 files for common parts, but also deduplicated storage of ANY number of files as lists of chunk hashes, pointing to just one copy of each chunk!

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#503

Post by cben »

In the hashing department:

- Zobrist hashing. It's completely incredible that such a trivial scheme is a near-perfect hash for sets. That's before you even consider the useful ability to compute hashes of related sets with added/removed-elements by simple XORing. (Caveat: I'm repeatedly tempted to use this magic for large sets; but it stops working well when number of elements > number of bits, because the matrix is over-determined, so there are easy-to-find subsets that contribute 0)

- Cuckoo hashing. Before going into the specific way it pushes around elements to usually fit exactly 1 per slot, there is a basic idea to grok that makes 2 possible places for an element work much better than 1: "the power of 2 choices". This is also the reason even a little load-balancing is effective. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.8... is a great overview.

- Merkle DAGs. Immutable content hashes are about the only non-painful form of distributed pointers humanity has found. OK, that's an idea not exactly an algorithm, but for example the easy ability to recursively diff 2 git trees is a neat algorithm.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#504

Post by api_or_ipa »

HereBeBeasties wrote: post #396
api_or_ipa wrote: post #353

Earlier quoted context omitted.

`git bisect` is an indispensible git trick. You give it commit where you know the bug exists, and one where you know it doesn't and it'll use binary search to help you find where the bug came from. It's absolutely wonderful.

I always struggle to see why people bang on about git bisect. You need tests to make it work. If you have tests, why aren't you running them continuously? If you're running them continuously, why do you need git bisect?

You don't really need automated tests. You can use a reproducible bug report as test input, then use git-diff to determine the first point it time it appears.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#505

Post by karakot »

wizeman wrote: post #456
karakot wrote: post #307

Earlier quoted context omitted.

and it's also a broken version.

Actually, I can definitely say that this version is not broken, i.e. I've formally proven it to be mathematically correct assuming that: 1. high and low are bigints (such as when using Python, for example) 2. the input array is sorted (needed for any binary search algorithm) 3. this missing code at the bottom is added: if (0 You can find the formal proof in WhyML below. This includes proofs that: 1. all array accesse…

thanks, this is a great comment(and the rest of the thread). Yes, I meant that it doesn't work without assuming #1, and it had missing #3.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#506

Post by HereBeBeasties »

Narretz wrote: post #412
HereBeBeasties wrote: post #396

Earlier quoted context omitted.

I always struggle to see why people bang on about git bisect. You need tests to make it work. If you have tests, why aren't you running them continuously? If you're running them continuously, why do you need git bisect?

If the bug is a regression, you write the test after finding it, and execute it with git-bisect. If the test starts to pass, you have the commit where it will fail.

If I can write a failing test, I can likely fix it. If I am interested in seeing who broke it and when, I can run git blame on the thing I'm fixing.

Given that my test suite is generally in the same repo as the code, I'd need to write something that patched my new test into the codebase at every git bisect commit, recompile and run it.

I can see that this may occasionally be useful if you have an extremely hard to find bug, but for me it's pretty rare. In fact I've done this once, ever.

Hence my skepticism when people describe this as "git's killer feature" or whatever other hyperbole.

Post reply on HN