21

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.

14
  • 25
    The existence of duplicates doesn't imply non-randomness. en.wikipedia.org/wiki/Birthday_paradox. Mar 3, 2012 at 23:31
  • 1
    And of course, a pseudo-random generator is, by definition, not at all random. Mar 3, 2012 at 23:34
  • 2
    @NayukiMinase: Math.random() generates a double-precision floating-point number, but the OP's test for equality works by converting those numbers to strings first, so unless the browser decides to include more than fifteen places past the decimal in its string representations, the OP is comparing values with much less entropy than that.
    – ruakh
    Mar 3, 2012 at 23:39
  • 2
    @delnan: You've misread the answer that you link to. According to that answer, there are roughly 7,036,874,417,766 double-precision floating-point numbers between 100.0 and 100.1. Between 0.0 and 1.0, there are about 2-to-the-power-of-62 double-precision floating-point numbers.
    – ruakh
    Mar 3, 2012 at 23:43
  • 1
    @pseudosavant: Are you sure about that? I would have thought that stringification of 5555555.5555555555555 might include a similar number of significant figures, and fewer places past the decimal-point, than stringification of 5.5555555555555.
    – ruakh
    Mar 4, 2012 at 1:57

3 Answers 3

32

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...

1
4

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

3
  • @BrianBallsun-Stanton: So it is. I've added a link to a snapshot of that page.
    – Tim Down
    Mar 11, 2013 at 10:26
  • blah that one is down now too :( Oct 22, 2013 at 2:40
  • @user1544793: Found another one.
    – Tim Down
    Oct 22, 2013 at 8:36
4

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.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.