如何用Mersenne Twister将无符号32位整数转为JS中[0,n]均匀分布整数？

Great question! When converting random 32-bit unsigned integers from a Mersenne Twister (or any PRNG) to a uniform integer in the range [0, n], the biggest pitfall is avoiding bias. The naive approach of mtRandom() % (n+1) works only if 2^32 is evenly divisible by n+1—which it almost never is. For example, if n=2, 2^32 = 4294967296 leaves a remainder of 1 when divided by 3, meaning the value 0 would be generated slightly more often than 1 or 2.

Below are two robust, unbiased solutions:

1. Rejection Sampling (Standard Approach) #

This method discards values that would introduce bias, ensuring every result in [0, n] has an equal probability.

How it works: #

• Calculate max: the largest 32-bit unsigned integer that's evenly divisible by n+1. This ensures any value ≤ max will map to [0, n] without bias when using modulo.
• Generate a random 32-bit int. If it's larger than max, discard it and try again.
• Once you get a valid value, use modulo to map it to [0, n].

JavaScript Implementation: #

// Assume mtRandom() returns an unsigned 32-bit integer (0 to 0xFFFFFFFF)
function getUniformInt(n) {
  if (n < 0 || n > 0xFFFFFFFF) {
    throw new RangeError('n must be between 0 and 2^32 - 1');
  }
  
  const range = n + 1;
  // Calculate the maximum valid value to avoid bias
  const max = 0xFFFFFFFF - (0xFFFFFFFF % range);
  
  let randomValue;
  // Reject values that would cause bias
  do {
    randomValue = mtRandom();
  } while (randomValue > max);
  
  // Map to [0, n]
  return randomValue % range;
}

2. Multiplicative Shift (Optimized Approach) #

If you want to avoid loops (even though rejection sampling rarely loops more than once for most n), this method uses integer multiplication and bit shifting to directly compute the unbiased value.

How it works: #

• Treat the random 32-bit int as a fraction of 2^32 (i.e., randomValue / 2^32, which is uniformly distributed in [0, 1)).
• Multiply this fraction by n+1 to get a value in [0, n+1), then take the integer part (which corresponds to the high 32 bits of the product when using 64-bit arithmetic).

JavaScript Implementation: #

// Assume mtRandom() returns an unsigned 32-bit integer (0 to 0xFFFFFFFF)
function getUniformIntOptimized(n) {
  if (n < 0 || n > 0xFFFFFFFF) {
    throw new RangeError('n must be between 0 and 2^32 - 1');
  }
  
  const range = BigInt(n + 1);
  const randomValue = BigInt(mtRandom());
  
  // Compute (randomValue * range) as a 64-bit integer, then take the high 32 bits
  const product = randomValue * range;
  const result = Number(product >> 32n);
  
  return result;
}

Key Notes: #

• Both methods produce perfectly uniform results. The multiplicative shift is slightly faster for large n (since it avoids loops), while rejection sampling is easier to understand and works without BigInt (though in JS, BigInt is necessary for the optimized version to handle 64-bit products).
• For edge cases:
  • If n = 0, both functions will return 0 immediately.
  • If n = 0xFFFFFFFF, the range is 2^32, so every random value is valid—both functions return the raw mtRandom() result.

内容的提问来源于stack exchange，提问作者Tree