Burrows-Wheeler transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf... Has something of Cantor's diagonal argument about it.
I always thought there was something almost magical about this one.
Ask HN: What's your favorite elegant/beautiful algorithm?
401–410 of 507 posts
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#402The Euclidean algorithm to compute the greatest common divisor of two numbers. In Javascript, if you have two numbers x and y that are both greater than zero, you compute the greatest common divisor xyGcd in one beautiful line of code: var xyGcd = function gcd(a,b){ return b ? gcd(b, a%b) : a; }(x, y); In my opinion this is the greatest one-liner ever.
Isn't it a-b instead of a%b?
a % b is a way to do it in fewer iterations than a - b.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#403Exponential backoff: I don't know if this is a published algorithm. Basically, background processes need to keep retrying an operation until it succeeds. (Make an API call to a server, upload a file, ect, ect.) If the retry interval is too small, you can DOS the remote server. (Server returns a 5xx error because there's a corner case that hits a defect.) But, if the retry interval is too large, your background proces…
Reminds me of the original Ethernet algorithm to deal with collisions on coax.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#404The Gilbert-Johnson-Keerthi convex shape intersection algorithm. It can take any two convex sets and tell you if they overlap, while converging on a separating axis or a penetration point, if it exists. All you need is a support function that returns a point in the set that is furthest along a given direction vector. The algorithm works in an arbitrary number of dimensions. Basically, it operates on a new shape which…
Wow. I'm surprised to see this on here. I used to work Johnson, he's is a super nice guy and always made time to have long conversations with me about optimization. I believe this algorithm is widely used in the video game industry?
Video games and anywhere you need a rigid body collision simulation. So TV & film visual effects is another common use.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#405The 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 with no further investigation. It is possible that different files will be thought identical. But it is unlikely that any two hashes ever generated by rsync have accidentally been the same when the underlying files were different.
(I do have to say "accidentally" because rsync uses MD5 as a hashing algorithm, and people have deliberately created collisions in MD5.)
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#406Earlier quoted context omitted.
No it absolutely is not. The lack of fundamental computer science knowledge in this thread is alarming.
Negative 2 points on a post saying that a computational method that possibly never terminates is not an algorithm... Oh dear...
It never terminates with probability 0.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#407Here are some algorithms that I find elegant / beautiful: - many recursive algorithms (I said why I think so, in another comment in this thread, agreeing with kamaal's comment about recursion - https://news.ycombinator.com/item?id=18236708 ), and recursive data structures too; to repeat: elegance and simplicity, although you have to think for a while to grok some of them - then it suddenly becomes clear how they work…
>Don't know the mathematical / cryptographical reason for it, if any.
I wonder if tptacek or any other crypto expert here can explain it. maybe there is some mathematical formula or principle behind the phenomenon I observed.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#408Earlier quoted context omitted.
Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.
I was curious how soon overflowing a native integer would come up. The "worst case" would be all "z"s (which map to 103), so how many characters does floor(log_103(2^n-1)) get you? int32 zzzz (4 characters) uint32 zzzz (4 characters) int64 zzzzzzzzz (9 characters) uint64 zzzzzzzzz (9 characters) But that's the worst case, not many real words have several "z"s in them. How often are real words affected? I did some exp…
Hmm, nice result. That makes me want to map letters onto primes in order of frequency. So "e" is 2, "t" is 3, etc., see: http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/...
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#409Earlier quoted context omitted.
I think you might be in the minority in this opinion. Many algorithms have pathological cases but are still considered algorithms
Minority? This is directly from Knuth.
Knuth defines effectiveness as: "... all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil."
K-means and other heuristic algorithms fit that description.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#410Earlier quoted context omitted.
> And in a general graph where negative edge-weights are permitted, it’s actually impossible to find the shortest path between two nodes without finding the shortest path between the source node and every other node! If there are negative edge-weights and cycles may occur, there is no shortest path between some nodes. You can keep going through a cycle whose total weight is negative getting "shorter" and "shorter". I…
Sure, but between "all edges have positive weights" and "there are cycles with negative total weight" there are still graphs that have negative edge weights, yet there's no negative-weight cycle. Example: V = { A, B, C } E = { A -> B, B -> C, C -> A } weight(A -> B) = 1 weight(B -> C) = 1 weight(C -> A) = -1
Right, yes.