Question 384089 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Why is number distribution not accurate when generating random integers using MAX_SAFE_INTEGER?

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.

Math.floor(Math.random() * Number.MAX_SAFE_INTEGER) // Always returns an odd number
Math.floor(Math.random() * (Number.MAX_SAFE_INTEGER - 1)) // Returns an odd number 75% of the time
Math.ceil(Math.random() * Number.MAX_SAFE_INTEGER) // Has a 50/50 chance to return odd or even

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?

class RandomNumberCounter {
    constructor() {
        this.evenCount = 0;
        this.oddCount = 0;
    }

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

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

const randomNumberCounter = new RandomNumberCounter();
randomNumberCounter.generateNumbersAndCount();
randomNumberCounter.printCounts();
Tags:

3

Answers


  1. 0

    @pointy highlighted the solution well. I’m just leaving here a working code that brings an equal ratio of even and odd numbers.

    The larger the boundary value of random number generation, the higher the probability of the result being even. If you double this value, the ratio will remain equal after many runs.

    So here the emphasis remains on fractions due to JavaScript’s floating-point number representation.

    Math.floor(
  Number.MAX_SAFE_INTEGER * (2 * Math.random())
);

    class RandomNumberCounter {
    constructor() {
        this.evenCount = 0;
        this.oddCount = 0;
        this.sumMathRandom = 0;
    }

    generateNumbersAndCount() {
        for (let i = 0; i < 10000000; i++) {
            // Changed
            const mathRandom = 2 * Math.random()
            const randomNumber = Math.floor(
              Number.MAX_SAFE_INTEGER * (mathRandom)
            );
            if (randomNumber % 2 === 0) {
                this.evenCount++;
            } else {
                this.oddCount++;
            }
            this.sumMathRandom += mathRandom
        }
    }

    printCounts() {
        console.log("Number of even numbers:", this.evenCount);
        console.log("Number of odd numbers:", this.oddCount);
        console.log("Avarage of Math.random:", this.sumMathRandom / 10000000);
    }
}

const randomNumberCounter = new RandomNumberCounter();
randomNumberCounter.generateNumbersAndCount();
randomNumberCounter.printCounts();
    Login or Signup to reply.
  2. 0

    Think about what binary floating point representation means, when you’re dealing with a value between 0 (inclusive) and 1 (exclusive). The integer part is always 0 (an even value), and the fractional part is represented by a sum of inverses of powers of 2: 1/2, 1/4, 1/8, 1/16, etc. Each 1 bit in the mantissa represents the presence of one of those inverse powers of two in the value.

    Thus, any random mantissa is going to be the inverse of an even value, because all the denominators are even. When you divide that even sum into an odd value (Number.MAX_SAFE_INTEGER), you have to get an odd result, because you can’t multiply an even number by an even number and get an odd result.

    Login or Signup to reply.
  3. 0

    First, you should multiply by 253 (Number.MAX_SAFE_INTEGER + 1) to get all 53 bits from a Math.random implementation that uses the full double precision. 253−1 probably doesn’t hurt much if it ever produces any different results at all, but I don’t feel like doing the necessary floating-point analysis – it’s much easier to just 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;
}

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

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search