javascript - When does Math.random() start repeating? - Stack Overflow

admin管理员组

文章数量:1308173

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);

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);

• javascript
• node.js
• random

Share Improve this question Follow edited Oct 26, 2018 at 6:04 avo asked Oct 26, 2018 at 5:29 avoavo 10.7k1313 gold badges5858 silver badges8888 bronze badges 8

• 2 This here probably answers it: hackernoon./… – dwjohnston Commented Oct 26, 2018 at 5:35
• One issue with your code, is that Math.random() is seeded on the current time, so even if / when it eventually finds a duplicate, your results arn't repeatable. – Ryan Leach Commented Oct 26, 2018 at 5:36
• I mean... it is intended to be random, not a repeating sequence of seemingly random numbers. I wouldn't expect it to start repeating... Unless I'm misunderstanding something... – Alexander Nied Commented Oct 26, 2018 at 5:36
• 1 Then you have an X Y problem. use UUID or a clock value that always increments, that resets when Date().valueOf() returns a different value. UUID's have a scheme involving a 'machine id' a local time source that can give you unique values for a very very long time. – Ryan Leach Commented Oct 26, 2018 at 5:44
• 1 @RyanTheLeach - I understand now. I didn't closely review your code and thought you were looking for sequential repetitions, not simply any one repeated value. Impressive it made it overnight w/o finding a duplicate, although by the end of the evening I wonder how long a single check would take to iterate over every value you'd recorded in v-- it may have slowed significantly... – Alexander Nied Commented Oct 26, 2018 at 5:45

 |  Show 3 more ments

2 Answers 2

Sorted by: Reset to default 7

It is browser specific:

https://www.ecma-international/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.

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 puters 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 you are generating 10,000 random numbers per second, you'd reach 50% probability in approximately 737 hours, which is just under 31 days. Less fortunately, even at 10,000 per second, it would take approximately 195,468 hours (which is approximately 22.3 years) to reach 100% probability.

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

Also, beware the Gambler's fallacy - the fact that you just generated a value doesn't make it any less likely that the same value will occur again. So, regardless of how many times you've already generated a particular value, the probability of the next random number being the same value is still 1/N (with N being the number of possible values).

本文标签： javascriptWhen does Mathrandom() start repeatingStack Overflow