Why is Google Chrome's Math.random number generator not *that* random?

Question

I ran into an odd "bug" today when I was running some unit tests in various browsers. I had run the tests in Firefox many times before today, and even IE but apparently not Chrome (v19-dev) yet. When I ran them in Chrome it consistently failed one test because two values I was calculating did not match.

When I really dug into what was happening I realized that the issue was that I was assuming that if I filled an array with 100,000 Math.random() values that they would all be unique (there wouldn't be any collisions). Turned out that in Chrome that is not true.

In Chrome I was consistently getting at least two pairs of values that matched out of 100,000. Firefox and IE9 never experience a collision. Here is a jsfiddle I wrote just for testing this that creates 1M Math.random() entries in an array: http://jsfiddle.net/pseudosavant/bcduj/

Does anyone know why the Chrome pseudo-random number generator that is used for Math.random is really not that random? It seems like this could have implications for any client-side js encryption routines that ever use Math.random.

Answer 1

See https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d:

If we analyze the first sub-generator independently we see that it has 32 bits of internal state. It’s not a full-cycle generator — its actual cycle length is about 590 million (18,030*2¹⁵-1, the math is tricky but it’s explained here and here, or you can just trust me). So we can only produce a maximum of 590 million distinct request identifiers with this generator. If they were randomly selected there would be a 50% chance of collision after generating just 30,000 identifiers.

Answer 2

Other answers have explained the issue. If you're after better pseudo-random number generation in JavaScript, I'd recommend this page as a good place to start:

http://baagoe.com/en/RandomMusings/javascript/

I adapted one of the algorithms on this page for a script I'm using to generate UUIDs in the browser and had no collisions in my tests.

UPDATE 22 October 2013

The pages linked to above are no longer live. Here's a link to a snapshot from the Wayback Machine:

http://web.archive.org/web/20120502223108/http://baagoe.com/en/RandomMusings/javascript/

And here's a link to a Node.js module that includes Alea.js:

https://npmjs.org/package/alea

Answer 3

Apparently Math.random() in V8 only works with 32 bit values (and didn't even correctly randomize all of those in the past). And with 32 bits, the probability of a collision reaches 50% around 2^16 = 65k values...