When does Math.random() start repeating?

问题:

I have this simple test in nodejs, I left it running overnight and could not get Math.random() to repeat. I realize that sooner or later the values (or even the whole sequence) will repeat, but is there any reasonable expectancy as to when it is going to happen?

let v = {};
for (let i = 0;; i++) {
  let r = Math.random();
  if (r in v) break;
  v[r] = r;
}
console.log(i);

回答1:

It is browser specific:

https://www.ecma-international.org/ecma-262/6.0/#sec-math.random

20.2.2.27 Math.random ( ) Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

Each Math.random function created for distinct code Realms must produce a distinct sequence of values from successive calls.

The requirement here is just pseudo-random with uniform distribution.

Here's a blog post from V8 (Chrome and NodeJs's Javascript Engine).

https://v8.dev/blog/math-random

Where they say they are using xorshift128+, which has a maximal period of 2^128 -1.

回答2:

Related (on another site): Acceptable to rely on random ints being unique?

Also extremely related: How many double numbers are there between 0.0 and 1.0?

Mathematically, there are an infinite number of real numbers between 0 and 1. However, there are only a finite number of possible values that Math.Random could generate (because computers only have a finite number of bits to represent numbers). Let's say that there are N possible values that it could generate. Then, by the Pigeonhole Principle, there is a 100% chance of getting at least one duplicate value once you generate exactly N + 1 values.

At this point, the Birthday Paradox demonstrates that you should start seeing duplicates surprisingly quickly. According to this "paradox" (which isn't a true paradox, just counterintuitive), given a room with only 23 people, there's a greater than 50% chance of two of them having the same birthday.

Returning to our example, the rule of thumb for calculating this (see the linked Wikipedia article) suggests that Math.Random reaches a 50% probability of duplicates once you generate approximately sqrt(N) numbers.

From the linked Stack Overflow question, if we assume that there are 7,036,874,417,766 numbers between 0 and 1 like the accepted answer says (and please read the linked question for a more detailed explanation of how many there actually are), then sqrt(7036874417766) is just over 2.652 million, which isn't actually all that many. If this is the case, you could reach 50% probability in around an hour. Unfortunately, even at 10,000 per second, it would take approximately 195,468 hours to reach 100% probability.

Some of the other answers give much higher figures for how many numbers there are, so take your pick.