4

In JavaScript, will this expression ever evaluate to true in any browser? Why or why not?

  Math.random() === Math.random()

Note: Please do take the above code literally. I'm not asking if Math.random will ever generate duplicate values.

Note2: no monkey-patching

This question is about the internal Implementation of Math.random(), not about the nature of random numbers.

Kara
  • 6,115
  • 16
  • 50
  • 57
Gil Birman
  • 35,242
  • 14
  • 75
  • 119
  • 3
    Yes, it's possible, but very unlikely. Why are you asking this? Do you mean "*ever*" literally? – Bergi Jul 06 '15 at 23:07
  • Practically speaking? Not likely. Theoretically, it's just an algorithm & seed to generate a "psuedo-random" value, but it only ever generates a value between 0 and 1. That's a large but finite set of possibilities, so of course it's possible, if very unlikely. – mc01 Jul 06 '15 at 23:09
  • 1
    The question is whether the same number will appear twice in a row, which is different from whether the same number will come up twice. – Rick Hitchcock Jul 06 '15 at 23:10
  • 1
    Yes, it is possible. take a look on this issue on chromium browser https://code.google.com/p/chromium/issues/detail?id=276886 . – vasilenicusor Jul 06 '15 at 23:12
  • @RickHitchcock: If it wouldn't, it wouldn't be random any more. – Bergi Jul 06 '15 at 23:12
  • 1
    Agreed, but we know that the algorithm isn't truly random. – Rick Hitchcock Jul 06 '15 at 23:14
  • This made me think of [Quantum mechanics](http://physics.stackexchange.com/a/15365). – blex Jul 06 '15 at 23:15
  • 1
    @vasilenicusor, your link shows that numbers may repeat more often than they should, but it doesn't show that consecutive numbers will repeat. – Rick Hitchcock Jul 06 '15 at 23:16
  • @GilBirman: Can you give some feedback on the answers? I'm not sure what your idea of a satisfactory answer is. – Nayuki Jul 07 '15 at 01:21

5 Answers5

6

Will the expression Math.random() === Math.random() ever evaluate to true in any browser?

Yes, and it's likely to have happened already.

This question is about the internal Implementation of Math.random()

Well, there isn't a single implementation, every javascript engine does implement its own one. Its randomness cannot be trusted, but common engines do/did use 31, 32, 48 or 52 bits of entropy.
This means that the probability of getting the same value from two consecutive calls (or, from any two calls) is 2-31, 2-32 etc. That doesn't sound much, but 231 is just about the number of internet users…

Oh, and of course there are always bugs like this one…

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Likely to have happened already? You must be referring to someone generating the same 32-bit number that someone else did in the past. If you're referring to the odds of `Math.random() === Math.random()` evaluating to `true`, it's actually very unlikely. Especially since there's no reason anyone would use that line of code in a program. – Beejor Aug 13 '15 at 03:12
  • @Beejor: I meant a `Math.random()` call giving the same result as the previous `Math.random()` call on that web page. So not to "someone else in the past", but indeed not necessarily within the expression `Math.random() === Math.random()`. – Bergi Aug 13 '15 at 03:30
4

Yes. As long as there's a limit on numeric precision, a random number algorithm always has the possibility of collision (generating two identical values).

JavaScript's Math.random() function returns a random number equal to 0 <= N < 1. In the real world, N is theoretically infinite. In computing, the limited precision of the result of any random() function results in a finite result set.

JavaScript uses signed 64-bit doubles, but the random() function doesn't return negative values. So the maximum range of unique return values is equivalent to a 32-bit unsigned integer.

Therefore the odds of Math.random() === Math.random() evaluating to true are around 1 in 4294967296^2, or 1 in 1.8e19, or 1 in 18 quintillion.

For this to happen in practice, it would require the function running in a loop and executing one billion times per second ( 1 GHz ) for around 500 years. Or you could get lucky on your first try. ;-)

Beejor
  • 8,606
  • 1
  • 41
  • 31
  • 1 to 2 MHz seem to be more realistic. So instead of testing myself, I'd rather put it on a popular website and let its visitors run the script :-) And the one who finds a collision [gets a car of course](https://xkcd.com/570/)! – Bergi Aug 13 '15 at 03:58
  • Looks rather slow to me… Btw, what is `raise(…)` supposed to do? Also it doesn't stop the script; not even the current interval. – Bergi Aug 13 '15 at 04:07
  • re: `raise` looks like he mixed some ruby code in with JS – Gil Birman Aug 13 '15 at 06:53
  • The `raise` was an error on my part; the correct keyword is `throw` (to exit the script in a pinch). Not to worry; the odds of ever reaching that line are essentially nil! But yeah, not sure what I was thinking with the "Faster" button since there's almost certainly a limit in JS for how many intervals can run before taking a speed hit, like a max 1ms shared frequency or something. – Beejor Mar 02 '19 at 01:42
  • "So the maximum range of unique return values is equivalent to a 32-bit unsigned integer." - No, there are way more than 2^32 unique `double` values in the range [0.0, 1.0); in fact there are at least 2^53 such values. – Nayuki Nov 21 '22 at 17:29
  • "Therefore the odds of Math.random() === Math.random() evaluating to true are around 1 in 4294967296^2" - Also no. A die has 6 sides. What is the chance of `diceRoll() == diceRoll()`? It's 1/6, not 1/6^2. – Nayuki Nov 21 '22 at 17:29
1

For a reasonable implementation, it is true with a probability of approximately 2−53.

This is because a common way to generate a random double is to evaluate: randomUint53() / (double)(1L << 53).

Example code: java.util.Random.nextDouble().

Nayuki
  • 17,911
  • 6
  • 53
  • 80
  • 1
    Can you expand on how you got that probability? – MT0 Jul 06 '15 at 23:06
  • OP is asking about javascript, not java! – Bergi Jul 06 '15 at 23:13
  • @ManojKumar: Not relevant. `Math.random` doesn't return integers, it returns doubles between 0 and 1. – Bergi Jul 06 '15 at 23:14
  • @Bergi: I disagree with your comment about JavaScript vs. Java. The underlying concepts are the same in both languages with respect to this question. The underlying raw random number generator would produce integers, and get converted to a `double` for `Math.random()`. – Nayuki Jul 07 '15 at 01:11
  • Yeah, just OP asked specifically for JS implementations. – Bergi Jul 07 '15 at 02:15
  • @Bergi IEEE 754 floating-point numbers work the same in JavaScript, Java, Python, C, etc. I already said that a reasonable implementation of `Math.random()` will generate a random integer in the range [0, 2^53) and divide it by 2^53 to yield a number in the range [0.0, 1.0). – Nayuki Nov 21 '22 at 17:26
0

Sure it can, assuming something like this is run before hand:

Math.random = function () {return 4;}

Otherwise, barring a bug in the browser implementation, it's theoretically possible, but I'd still say the answer to "will this ever evaluate to true" is "no". It's just too tiny a probability to realistically ever happen.

Retsam
  • 30,909
  • 11
  • 68
  • 90
  • So, what is the probability, and what is "too tiny"? Not likely to happen before the heat death of the universe? – Bergi Jul 07 '15 at 00:43
  • @Bergi It depends on the rate at which the function is run. Based on the fact we have things like Seti@Home that's used like a quarter billion dollars worth of energy to look for aliens, maybe someone will start a Random@Home project at get us a collision in a few years. A few tons of pollution, but... science! ;-) – Beejor Aug 13 '15 at 03:42
  • 1
    A homage to https://xkcd.com/221/ – Nayuki Nov 21 '22 at 17:34
0

Not possible, as per V8 (Chrome) implementation: https://hackernoon.com/how-does-javascripts-math-random-generate-random-numbers-ef0de6a20131.

Ahmed Mahmoud
  • 1,479
  • 2
  • 12
  • 18