javascript - Probability of getting the same value using Math.random

Question

The requirement is to send a unique id to database when user click on submit button. So I am using Javascript Math.random method. I just want to know what are the chances or possibility to get same number and what bit size of using Math.random.

Answer 1

You're up against something called the birthday problem: even though there are 366 possible birthdays, when you get only 26 people in a room, the chance that some pair will have the same birthday is better than 50-50. In general, collisions are likely when your numbers approach the square root of the sample size (26 is in the neighborhood of the square root of 366).

Javascript's Math.random() has about 52 bits of randomness. Therefore, collisions should be likely as your record count approaches 2**26, which is about 60 million, a quite modest size for a database.

You should use a cryptographically-secure PRNG with at least 128 bits, preferably 256, to avoid collisions. There are probably ready-to-use UUID libraries for this available.

For an given number of keys k, and a keyspace N, the approximate odds of collision are:

1 - exp((-k * (k-1))/(2 * N))

So for k=1 million records, N=2**52, that comes to about 1 in 9000, if I did the math right. That's further assuming that Javascript's Math.random() is truly using the fill 52 bits of randomness available to it...that too is an assumption I wouldn't make.