4 ms·
That's a nifty algorithm. Sillysaurus3's wonderful explanation from last year helped me figure out what's happening. Mostly, at least (my fault, not his): h
by nkurz 12y ago
That's a nifty algorithm. Sillysaurus3's wonderful explanation from last year helped me figure out what's happening. Mostly, at least (my fault, not his):
https://news.ycombinator.com/item?id=8140385 https://news.ycombinator.com/item?id=8140385
It feels like there should be some faster way of doing the jump calculation that doesn't require the floating point divide. Relatively, it's a slow and expensive operation, and doing ln(n) of them on each bucket lookup would add up to a lot if you have lots of buckets.
- ChrisLomont 12y agoHis explanation has mistakes. For example, in step 1 he claims "After this multiplication, the first 4 bytes and the last 4 bytes of 'key' are nonzero" Take any 8 byte value b, multiply by 16133697096952638549ULL (mod 2^64) to get a value for the key. Now key * 2862933555777941757ULL = b. Thus there is an input value for key that I can make hit any number. The first and last 4 bytes are thus certainly not always nonzero. He then uses "The fact that the first 4 bytes become nonzero is important for the next step" and proceeds. This is wrong. For a concrete example, suppose key is 16133697096952638549ULL. Then key * 2862933555777941757ULL = 1. The first 7 bytes (actually, the first 63 bits) are all zero. Adding 1 as in the code still leaves the first 62 bits zero. (the value 16133697096952638549ULL is the multiplicative inverse of the constant in the algorithm mod 2^64).