Does using modulo (%) affect quality of randomness?
Using modulo (%) to reduce a random number to a smaller range can introduce bias if the range does not evenly divide the original range. Common methods like `rand() % N` often produce non-uniform results, especially with small N or poor PRNGs. Techniques like rejection sampling or floating-point conversion are recommended to preserve randomness quality.
Background
- This Stack Exchange question touches on a classic problem in software engineering: how to convert a raw random number (e.g., from a random-number generator, or RNG) into a smaller range without introducing bias.
- The "modulo bias" issue: if you generate a random integer in a range 0–RAND_MAX and then take `value % N` to get a range 0–N-1, the result is uniformly distributed only if RAND_MAX+1 is an exact multiple of N. Otherwise, some outputs appear slightly more often. The bias grows as N gets close to RAND_MAX.
- Common workarounds: rejection sampling (discard out-of-range values and retry), or more sophisticated algorithms (e.g., Lemire's nearly-divisionless technique).
- The question is relevant to anyone writing simulations, games, cryptography, or any application requiring fair dice rolls, random sampling, or statistical uniformity — where even small biases can break correctness or security.