Re:Distributed count distinct vs. HyperLogLog in Postgres
by ignoramous on Friday December 22, 2017 @11:27PM
(#15992931)
Find a nonce such that hash(x + nonce) has n leading zeroes, and you've invented Proof of Work :)
It is amazing how different techniques add up, but almost exclusively base off of a novel, mathematically sound, fundamental piece of computer science.
Say you have a random hash function that produces (unsigned) int values. So, for all inputs, hash(x) will be in the range [0, 2^32).
- How many different inputs would you need to feed it before you would expect to see hash(x) == 0?
... uh, like, billions?
- How many different inputs would you need to feed it before you would expect to see hash(x) < 2?
... well, still in the billions, but maybe half as many as finding hash(x) == 0..
- How many different inputs would you need to feed it before you would expect to see hash(x) < 4? .. 8? .. 16? .. 32? ... all the way up to < 2^31 (typically you'll see this within two tries) and 2^32 (all of them).
... and so on and so forth; math does the rest. The "count the leading zeroes" check is the same as "the hashcode is less than 2^X". To prevent a single "lucky" hash from throwing off your estimate, you process your inputs in batches and average their estimates.