Why are random integers generated by multiplying by MAX_SAFE_INTEGER not evenly distributed between odd and even?

Trying to generate a number using MAX_SAFE_INTEGER I noticed something strange, I'm sure it has to do with the way numbers are stored in JavaScript, but I don't understand what exactly it is.

// Always returns an odd number
Math.floor(Math.random() * Number.MAX_SAFE_INTEGER)

// Returns an odd number 75% of the time
Math.floor(Math.random() * (Number.MAX_SAFE_INTEGER - 1))

// Has a 50/50 chance to return odd or even
Math.ceil(Math.random() * Number.MAX_SAFE_INTEGER)

How can this behavior be explained and what would be the largest integer you can use in Math.floor to get a 50/50 ratio?

let evenCount = 0, oddCount = 0;

for (let i = 0; i < 10000; i++) {
  const randomNumber = Math.floor(Math.random() * Number.MAX_SAFE_INTEGER);
  if (randomNumber % 2 === 0) {
    evenCount++;
  } else {
    oddCount++;
  }
}

console.log("Number of even numbers:", evenCount);
console.log("Number of odd numbers:", oddCount);

Solution

First, you should multiply by 2⁵³ (Number.MAX_SAFE_INTEGER + 1) to get all 53 bits from a Math.random implementation that uses the full double precision. 2⁵³−1 doesn’t hurt much (it maps both 0 and 2⁻⁵³ to 0, producing a tiny bias), but it’s better to pick the solution that’s obviously correct.

But then what’s the issue? Well, your original code works fine on Firefox and Safari! It’s just that V8 (i.e. Chrome and derivatives) uses 52 bits instead of 53.

let mostBits = 0;

for (let i = 0; i < 10000; i++) {
    const bits = Math.random().toString(2).slice(2).length;
    if (bits > mostBits) {
        mostBits = bits;
    }
}

console.log("Most bits:", mostBits);

(Firefox, Safari)

Most bits: 53

(Chrome)

Most bits: 52

(The reason that you can store 53 bits accurately with a significand with 52 bits of storage is that the integer part is implicitly a 1 that can be scaled to the right place by the exponent, same as why Number.MAX_SAFE_INTEGER is what it is.)

Looking at the relevant part of V8’s implementation, I assume the only reason it does this is for performance – by fixing the exponent to make the range [1, 2), it can insert the random bits directly into the double instead of having to perform a multiplication.

static inline double ToDouble(uint64_t state0) {
  // Exponent for double values for [1.0 .. 2.0)
  static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
  uint64_t random = (state0 >> 12) | kExponentBits;
  return base::bit_cast<double>(random) - 1;
}

Why does multiplying a number in the final result’s range by 2⁵³−1 and then flooring it always produce an odd number?

(2⁵³−1)x = 2⁵³ x − x (exactly)
2⁵³ x is always even
In order for 2⁵³ x − x to round to the exact floating-point value 2⁵³ x (and therefore be an even number), x has to be smaller than 2⁵³ x’s ULP (unit in the last place) – which it never can be! x’s ULP is 1/2⁵³ of the value of its most significant bit, which is ≤ x.

So to answer your question,

what would be the largest integer you can use in Math.floor to get a 50/50 ratio?

At most 2⁵², but I wouldn’t count on Math.random having more than 32 bits of randomness unless you’re only targeting one engine (V8 changed to 52 in 2015, for example), or even on it being good enough randomness for a particular purpose – none of this stuff is in the spec.

This function returns a Number value with positive sign, greater than or equal to +0 but strictly less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-defined algorithm or strategy.

You might want to consider implementing a known PRNG in JavaScript and seeding it with strong randomness from crypto.getRandomValues.