Random Number Generator

Why random % n is not a fair way to pick

Take a random integer from 0 up to m − 1 and reduce it modulo n. Every outcome gets ⌊m/n⌋ chances — and then the m mod n values left over get one more each. So unless n divides m exactly, the first few outcomes are simply more likely than the rest, by a factor of (base + 1) ⁄ base.

How much that matters depends entirely on how big the source is:

A 32-bit source with a small n is genuinely invisible — not “small enough to ignore”, but below anything anyone will ever measure. A 15-bit source with a large n is a real defect: reducing a value under 32,768 modulo 10,000 makes 2,768 of the outcomes a third more likely than the other 7,232.

That combination is not hypothetical. It is exactly what rand() % n does in C wherever RAND_MAX is 32,767 — the minimum the standard permits, and what Microsoft's runtime actually uses.

The fix is to throw some numbers away

You cannot divide 32,768 things evenly into 10,000 boxes, so the honest options are to make the source bigger or to reject the leftovers and draw again. Rejection sampling discards anything at or above the largest exact multiple of n — 30,000 in that case — and costs about 1.092 draws per result in exchange for exact uniformity.

JavaScript sidesteps the problem: Math.random() returns a float, so Math.floor(Math.random() * n) is uniform to the limits of the double it came from. The bias belongs to integer sources — and it is worth knowing about precisely because it is invisible in testing. The distribution looks flat until you count carefully enough, which is also how it is easy to measure wrongly: comparing the most common outcome against the least common one across ten thousand buckets reports a ratio near 1.8, almost all of which is sampling noise rather than bias.