Modulo bias: how random() % 45 quietly favours low numbers

Suppose you have a perfect source of random bytes — say crypto.getRandomValues() — and you want a lottery number from 1 to 45. The obvious code is one line:

const n = (randomByte % 45) + 1;   // WRONG: biased

This is the single most common randomness bug in real code, and the reason the OpenBSD C library ships a dedicated function, arc4random_uniform(), whose documentation exists specifically to warn against constructions like arc4random() % upper_bound because of what it calls "modulo bias". Let's work the bias out exactly.

The pigeonhole problem

A random byte takes one of 256 values: 0 through 255. We want to fold those onto 45 outcomes. But 256 is not a multiple of 45:

256 = 5 × 45 + 31

So the folding cannot be even. Divide 0–255 by remainder:

• Values 0–224 (that's 225 = 5 × 45 values) fold onto the 45 outcomes exactly 5 times each.
• The leftover 31 values, 225–255, fold onto remainders 0 through 30 — giving those outcomes a 6th hit.

Check the count: 31 outcomes × 6 hits + 14 outcomes × 5 hits = 186 + 70 = 256. ✔

After the + 1, that means:

Numbers 1 through 31 each come up with probability 6/256; numbers 32 through 45 with probability 5/256. The ratio is 6/5 = 1.2 — every low number is a full 20% more likely than every high number. A "random" pick from this generator lands in 1–31 with probability 31 × 6/256 = 186/256 ≈ 72.7%, versus the fair 31/45 ≈ 68.9%.

Nothing was wrong with the random bytes. The bytes were perfect. The mapping threw fairness away.

"But 8 bits is a toy example — real code uses 32 bits"

It does, and the bias shrinks — but never to zero, and the arithmetic is worth seeing because it rhymes beautifully. For a 32-bit word there are 2^32 = 4,294,967,296 values, and:

4,294,967,296 mod 45 = 31

(The same remainder is no coincidence: 2^32 = (2^8)^4, and 31^4 mod 45 cycles back to 31.) So again exactly 31 outcomes get one extra hit — but now it's one extra out of ~95.4 million hits each: values 0–4,294,967,264 cover each outcome 95,443,717 times, and outcomes 1–31 get hit number 95,443,718. The skew is a factor of 95,443,718 / 95,443,717 ≈ 1.00000001 — about one part in 95 million.

Practically undetectable? For one player, yes. Which invites the question this article exists to answer.

Why small bias still matters

1. Fairness claims are absolute, not approximate. A generator advertised as uniform either is or isn't. "Uniform except numbers 1–31 are slightly favoured" is a different product — and in regulated gambling it's a failing one: certification standards for gaming RNGs explicitly require that scaling raw output onto game ranges must not introduce bias (see what RNG certification actually checks). The 8-bit version of the bug would fail a lab test in minutes.

2. Bias compounds over volume. A draw site serves millions of picks. With the 8-bit bug, in 100,000 picks each low number is expected 6/256 × 100,000 ≈ 2,344 times and each high number 5/256 × 100,000 ≈ 1,953 times — a gap of about 390 appearances per number, glaring to a chi-square test. You can reproduce exactly this experiment with our randomness tester.

3. The bug's size is an accident of the numbers. The bias is (leftover count)/(total count), and the leftover is 2^k mod n — it depends on the arithmetic relationship between your word size and your range, not on any engineering judgement. Change the game from 45 balls to 47 and the bias changes; nobody reviews it because nobody chose it. A correctness property that varies silently with unrelated constants is exactly the kind of thing engineering standards exist to forbid.

4. It undermines the audit trail. This site's core rule is that every claim is backed by a shown calculation. "Our picks are uniform" is only checkable if the mapping is exactly uniform — then anyone can verify the whole pipeline by testing outputs. A knowingly-tolerated small bias converts a provable statement into a judgement call.

The shape of the fix

The fix is not a better formula — no formula can split 256 values evenly into 45 buckets, ever; that's the pigeonhole principle. The fix is to refuse to use the leftover values: if the byte lands in the 31-value overflow zone, throw it away and draw again. That's called rejection sampling, it makes the output exactly uniform rather than approximately, and it costs almost nothing — on average about 1.14 draws per number in the 8-bit case. We work through it, including the retry mathematics, in rejection sampling explained, and show it running in production in how we built an unbiased generator.

The one-sentence takeaway: perfect random bytes plus the % operator equals a biased draw — the leftover 2^k mod n values always favour the low end, and for 8-bit words mapped to 45 numbers the favouritism is a measurable 20%.