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

451–460 of 507 posts

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

#451

Post by romwell »

_pastel wrote: post #431
muzzio wrote: post #303

Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…

I have a pet implementation of the frequency map that I'm overly fond of, for ascii strings: (1) keep an array of length 127 that you re-use and set to 0 between calls (2) for each character in the first string, increment the array at the character's index (3) for each character in the second string, decrement the array at the character's index If you end up with all 0s, it's an anagram.

Given the constraints of the problem, it's the sanest thing to do.

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

#453

Post by gwilliams »

icgrep (http://www.icgrep.com) has a clever approach to searching text for arbitrary sets of characters in a parallel manner. If 128-bit registers are available and we're processing 8-bit characters (for example), the next 128 characters from a file are first loaded into 8 SIMD registers. Then a bitwise transposition is performed so that r0 contains bit 0 of each input character, r1 contains bit 1, etc., up to r7. Then with a series of logic operations across those registers (imagine the sum-of-product result of a k-map of characters of interest), searches for any arbitrary subset of characters can be performed in parallel, leaving 1s in the corresponding position of the result register for each match and 0s elsewhere. icgrep supports full regex patterns and Unicode (using 21 registers instead of 8), but what interests me are the elegant transpose and logic steps.

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

#454

Post by akhilcacharya »

jules wrote: post #369
lifthrasiir wrote: post #192

Earlier quoted context omitted.

If f is monotonic and continuous, you can solve f(x) = y for x by successively narrowing an interval [a, b] where f(a) <= y <= f(b) (or vice versa for decreasing functions). In the case that the range of f spans the entire real numbers, the initial range can be determined as the smallest range [-2^k, 2^k] where k is an integer (a strategy often used for open-ended binary search).

Interestingly, with floats you can also binary search on the binary representation. That narrows down the answer to the most precise answer representable in floating point in at most 64 steps for 64 bit floats. If you bisect the interval in the middle at each step, then it could take more steps (possibly more than 1000). It turns out that doing this is pretty much equivalent to what you suggest, if you narrow down th…

Interesting! I didn't really think about this but this is how I implemented sqrt() and division in an interview. Didn't think of how it generalizes!

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

#456

Post by wizeman »

karakot wrote: post #307
jules wrote: post #279

Earlier quoted context omitted.

I like this version: low = -1 high = arr.length while(high - low > 1){ mid = (high + low)/2 if(arr[mid] This eliminates all branches from the body of the loop (gets compiled to conditional move). It's also more general because it can be used to find the right position to insert a new element in a sorted array.

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 accesses are in bounds [checked automatically]

2. there is no undefined behavior (such as division by zero) [checked automatically]

3. the function always terminates [enforced automatically, proven with the help of the 'variant' clause]

4. there are no overflows [checked automatically, not possible since we're using bigints]

5. if an index is returned, the array has an element with value equal to x at that index [the 'ensures' clause]

6. if instead the function returns "not found", the array does not have any element with a value equal to x [the 'raises' clause]

... all this assuming that the input array is sorted [the 'requires' clause]

Code + proof here (it makes more sense if you can read OCaml syntax): https://clbin.com/jbTk8

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

#457

Post by DarkWiiPlayer »

_pastel wrote: post #431
muzzio wrote: post #303

Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…

I have a pet implementation of the frequency map that I'm overly fond of, for ascii strings: (1) keep an array of length 127 that you re-use and set to 0 between calls (2) for each character in the first string, increment the array at the character's index (3) for each character in the second string, decrement the array at the character's index If you end up with all 0s, it's an anagram.

Doesn't that mean in the end you have to check 127 values for if they are 0?

Or 64, if you store numbers as 32-bit integers and compare them as 64-bit using a union type.

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

#458

Post by thijsvandien »

LukeShu wrote: post #388
amelius wrote: post #326

Earlier 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…

Now add support for Unicode. :)

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

#459

Post by luxcem »

ArtWomb wrote: post #217
gregordv wrote: post #170

I always push my devs to really study the Bittorrent protocol. The elements of the protocol are all fairly easy to understand, but it's gorgeous to see how elegantly it solved a social problem rather than a computational problem. The tit-for-tat and fast-finish protocols are incredibly graceful ways to create virtuous cycles in a social/technical hybrid, and replaced very real vicious cycles in previous protocols. Va…

BitTorrent is foundational to the rise of decentralized stores and sharing: IPFS, Dat Protocol, WebTorrent, Storj, Holochain, etc. An Introduction to Kademlia DHT & How It Works http://gleamly.com/article/introduction-kademlia-dht-how-it-...

DHT Algorithms are nice, the Chord is really simple and easy to understand.

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

#460

Post by yread »

candiodari wrote: post #236
yread wrote: post #162

Earlier quoted context omitted.

I would also vote for FFT. It's amazing how widely it's used and what sort of tricks you can do in frequency domain. Multiplying polynomials? Simple! Multiple 2D projections of a 3D object? Just FFT them, do a couple of simple steps and you will get a 3D model.

Do you have some details for these applications ?

The multiplication is concisely described here http://numbers.computation.free.fr/Constants/Algorithms/fft....

For 2D -> 3D, see https://en.wikipedia.org/wiki/Projection-slice_theorem for a simple overview

Post reply on HN