3 ms·

2^63 allows giving each of the 8 billion people on earth over a billion numbers each with no repeats. 19 digits is plenty, since it only takes 10 digits to coun

• FabHK 4y ago
  To elaborate: There are about 8 * 10^9 people, or nearly 10^10. So, if you allocate numbers sequentially with a central authority, 10 digits would be enough. The birthday paradox says that probability of collision with random identifiers becomes very big (a half or so) as soon as the number of instances approaches the square root of the number of available identifiers. In other words, if we used 20 digits, the birthday paradox rule of thumb would predict a probability of collision of around a half. (That is borne out by Lemire's table, which states 27%, which is close enough given the approximations here). The solution proposed here is to use at least 30 digits; I wonder whether that is a good rule of thumb in general: to avoid collisions with a N-bit hash function, do not hash more than 2^(N/3) elements. At any rate, hashing the 2^33 humans with 128 bits is good enough (probability of collision < 1e-18), and with 256 bits definitely.
• deleted 4y ago
  [deleted]