How to Generate Random Numbers Without Modulo Bias

Somewhere in almost every codebase that needs a random integer in a range, you'll find this line, or something functionally identical to it:

c

int roll = rand() % 6;

It compiles, it runs, it produces numbers between 0 and 5, and it looks correct. It is also, in the general case, subtly wrong — not wrong in the sense of crashing or throwing an exception, but wrong in the sense that some outputs are quietly more likely than others. The bug is silent because it doesn't fail any test that just checks "is the output in range." It only shows up when you check whether the output is uniform, which most code never bothers to verify.

This is modulo bias, and understanding exactly why it happens — not just that it happens — is what separates "I heard modulo is bad for randomness" from actually knowing when it matters and how to fix it.

What Modulo Bias Actually Is

A pseudo-random number generator (PRNG) produces integers uniformly across some fixed range — call it [0, M), meaning 0 up to but not including M. Most PRNGs are built around a source range that's a power of two, because that maps naturally onto binary hardware: a 32-bit generator produces values uniformly across [0, 2^32).

The problem arises when you want a different range than the one the generator naturally produces — say, integers from 0 to 5 for a die roll — and you get there with modulo: value % 6. This works fine when the source range is an exact multiple of 6. It fails when it isn't, and a 32-bit range is essentially never an exact multiple of an arbitrary target range like 6.

Why the Modulo Operation Creates Unequal Probabilities

The mechanism is straightforward once you see it laid out. Modulo maps a large range down to a smaller one by wrapping around repeatedly. If the source range divides evenly into the target range, each target value gets exactly the same number of source values mapped onto it, and the mapping stays uniform. If it doesn't divide evenly, there's a leftover chunk at the top of the source range that only gets to complete a partial cycle — and the target values inside that partial cycle end up overrepresented.

A Worked Numerical Example

Take the exact scenario worth working through by hand: a source generator producing values 0–9 (10 possible values), mapped with modulo into a target range of 0–5 (6 possible values).

Lay out every source value and where it lands:

source  0  1  2  3  4  5  6  7  8  9
target  0  1  2  3  4  5  0  1  2  3

Now count how many source values map to each target value:

target 0:  sources {0, 6}        → 2 occurrences
target 1:  sources {1, 7}        → 2 occurrences
target 2:  sources {2, 8}        → 2 occurrences
target 3:  sources {3, 9}        → 2 occurrences
target 4:  sources {4}           → 1 occurrence
target 5:  sources {5}           → 1 occurrence

Targets 0 through 3 each get hit by 2 out of 10 possible source values — a probability of 20% each. Targets 4 and 5 each get hit by only 1 out of 10 — a probability of 10% each. If this were a die roll, you'd be twice as likely to roll a 0, 1, 2, or 3 as you would a 4 or 5. That's not a rounding artifact or an edge case; it's a structural property of the mapping caused entirely by 10 not being evenly divisible by 6.

The general rule: with a source range of size M and a target range of size N, the bias exists whenever M mod N ≠ 0. The size of the bias is proportional to (M mod N) / M — which is why this example, with a tiny source range of 10, produces an obvious and large bias, while a 32-bit generator (M = 2^32 ≈ 4.29 billion) mapped onto a small range like 6 produces a bias so small it's statistically real but often invisible without a large sample and a formal test. The math is identical in both cases; only the magnitude changes.

Why Divisibility Is the Entire Problem

This is worth stating plainly because it's easy to reach for the wrong intuition: modulo bias isn't caused by a "bad" PRNG, and it isn't fixed by a "better" one. A cryptographically secure PRNG producing perfectly uniform output over [0, 2^32) will produce exactly the same proportional bias when reduced with % 6, because the bias comes from the arithmetic relationship between the source range and the target range, not from any flaw in the randomness source feeding it. Swapping rand() for a hardware RNG doesn't fix this bug; the bug is in the transformation, not the source.

Rejection Sampling

The standard, well-understood fix is rejection sampling: instead of forcing every source value into the target range via modulo, you discard (reject) any source value that falls into the "leftover" partial cycle, and only keep values that come from a portion of the source range that divides evenly into the target range.

Concretely, for the example above (source range 0–9, target range 0–5): the largest multiple of 6 that fits within 10 is 6 (covering source values 0–5). Source values 6, 7, 8, 9 fall outside that clean multiple and get discarded; if the generator produces one of them, you simply draw again. Every value that survives falls into an evenly-divisible portion of the range, so the resulting distribution over 0–5 is exactly uniform.

How Rejection Sampling Removes the Bias

Re-running the counting exercise makes this concrete. With values 6–9 rejected and redrawn, only source values 0–5 are ever kept, and each of them maps to exactly one target value:

target 0: source {0} → 1 occurrence (kept)
target 1: source {1} → 1 occurrence (kept)
target 2: source {2} → 1 occurrence (kept)
target 3: source {3} → 1 occurrence (kept)
target 4: source {4} → 1 occurrence (kept)
target 5: source {5} → 1 occurrence (kept)

Each target value now corresponds to exactly one kept source value — perfectly uniform, by construction, regardless of how many times a rejected draw had to be retried to get there.

Pseudocode for an Unbiased Implementation

function unbiasedRandom(n):          // returns uniform integer in [0, n)
    limit = floor(RAND_MAX / n) * n  // largest multiple of n that fits
    loop:
        r = rawRandom()              // draw from full source range [0, RAND_MAX)
        if r < limit:
            return r % n              // safe now — r falls in the clean region
        // else: r fell in the leftover region, discard and redraw

The key structural point: the modulo operation itself isn't the problem and doesn't disappear from the code — it's applied only after filtering out the values that would have caused bias, which is the part most naive implementations skip.

Practical Code Example in C

c

#include <stdint.h>
#include <stdlib.h>

uint32_t unbiased_random(uint32_t n) {
    uint32_t limit = (UINT32_MAX / n) * n;
    uint32_t r;
    do {
        r = arc4random(); // or another full-width PRNG source
    } while (r >= limit);
    return r % n;
}

Most production-grade standard libraries already implement this internally — Java's Random.nextInt(bound), Python's random.randrange(), and Go's math/rand.Intn() all perform some form of rejection or a mathematically equivalent bias-correction internally, precisely because naive modulo reduction is common enough to be worth guarding against at the library level. The practical lesson isn't "always write rejection sampling by hand" — it's "know whether the function you're calling already handles this, and don't reintroduce the bug by hand-rolling rand() % n when a bias-free standard function is sitting right there."

Performance Considerations

Rejection sampling's cost is the possibility of a redraw, and it's worth quantifying rather than assuming it's expensive. The probability of a rejection on any given draw is (M mod N) / M. For a 32-bit source and a small target range like 6, that probability is on the order of one in several hundred million — a redraw is so rare it has no measurable performance impact. The scenario where rejection rate actually matters is when the target range N is a large fraction of the source range M — for example, generating a value in [0, 3_000_000_000) from a 32-bit source, where the leftover region is a substantial fraction of the total range and redraws happen often enough to be worth optimizing (typically by using a wider source range, like 64-bit output, rather than tolerating a high rejection rate on a 32-bit one).

When Tiny Statistical Biases Actually Matter

Context determines whether this is worth fixing at all. For most everyday cases — a game randomly picking a background color, a UI shuffling a small non-critical list — a bias on the order of one part in a billion is completely irrelevant; no user or process will ever detect it, and correctness-obsessed rejection sampling there is arguably wasted engineering effort.

The cases where it genuinely matters share a common feature: either the sample size is enormous, or the stakes of the output are high enough that even a tiny statistical skew compounds into something detectable or exploitable.

Simulations run millions or billions of trials specifically to estimate probabilities precisely — a Monte Carlo simulation with even a small systematic bias in its random inputs will converge to a subtly wrong answer, and because the bias is systematic rather than noise, more trials don't average it out.

Randomized algorithms (randomized quicksort's pivot selection, skip list level generation, reservoir sampling) often rely on the theoretical uniform-distribution guarantee to achieve their expected-case performance bounds; a biased random source can degrade these algorithms toward their worst-case behavior in ways that are hard to diagnose because the code "works," just slower or less balanced than expected.

Shuffling is a classic failure point — the naive "shuffle with modulo" implementation of Fisher-Yates doesn't just introduce small statistical skew, it can produce certain permutations that are structurally impossible to generate at all, depending on how the bias compounds across each step of the shuffle. This is a well-documented, named failure mode (sometimes called the "modulo bias in shuffling" problem) precisely because it's been the source of real bugs in card-shuffling and playlist-shuffling code.

Sampling for statistics or A/B testing needs genuine uniformity, since a biased sampling method silently violates the independence assumptions most statistical tests rely on.

Identifiers and tokens generated with a biased method can, at large enough scale, produce a detectably skewed distribution of values — not usually a security issue in itself, but a correctness one if any downstream system assumes uniform distribution (for load balancing, for instance, where a biased hash-to-bucket assignment causes real, measurable load imbalance).

Statistical Randomness Versus Cryptographic Security

These are two different properties, and conflating them is a common and more serious mistake than modulo bias itself. Statistical randomness means the output is uniformly distributed and doesn't fail statistical tests for pattern or correlation. Cryptographic security means, additionally, that the output is unpredictable even to an adversary who has seen previous outputs and knows the algorithm — a much stronger property.

A cryptographically secure PRNG (CSPRNG) is always expected to be statistically uniform, but a statistically uniform PRNG is absolutely not automatically cryptographically secure. The Mersenne Twister, for instance, has excellent statistical properties and fails essentially every standard randomness test suite in the "this looks non-random" direction — but its internal state can be fully reconstructed from a modest number of observed outputs, making it completely unsuitable for anything security-sensitive (session tokens, password reset codes, cryptographic keys) despite being statistically fine for simulations and games. Anywhere unpredictability against an adversary matters, the correct tool is a CSPRNG (/dev/urandom, arc4random, crypto/rand in Go, SecureRandom in Java) — and note that a CSPRNG is just as susceptible to modulo bias as any other PRNG if you reduce its output with a naive modulo; cryptographic strength and unbiased range reduction are orthogonal properties, and fixing one does not fix the other.

Why a Good PRNG Doesn't Automatically Make a Transformation Unbiased

This is worth restating directly because it's the single most common misconception on this topic: the quality of the underlying random source and the correctness of the range-reduction transformation applied to it are independent concerns. A perfect, uniformly distributed, cryptographically secure random source fed through a naive modulo reduction produces exactly the same proportional bias as a weak PRNG fed through the same reduction. Upgrading the source fixes nothing if the transformation is the actual bug.

This distinction matters as a general engineering principle beyond random numbers specifically: observing that a system produces outputs that look varied or unpredictable from the outside tells you nothing about how those outputs were generated internally. A reader might come across a name or search phrase like Crazytower official while browsing interactive digital products and notice outcomes that appear random — but the public interface of any such product reveals nothing about which RNG, PRNG, or range-reduction method sits behind it, whether it uses rejection sampling, a modulo operation, or something else entirely. The only way to know the actual implementation is to inspect the code or documentation directly; visible behavior alone, however random it appears, is never sufficient evidence for how randomness was generated under the hood.

Common Implementation Mistakes

The most frequent mistake is exactly the pattern that opened this article — rand() % n — applied without checking whether n divides evenly into the generator's range, which it almost never does for arbitrary n.

A second, subtler mistake is assuming that using a wider integer type "dilutes" the bias into irrelevance without checking. This is often true in practice (as shown in the performance section) but isn't universally safe — if n happens to be a large fraction of the source range, the bias remains significant regardless of how wide the source integer is, because what matters is the ratio (M mod N) / M, not the absolute size of M.

A third mistake is implementing rejection sampling but computing the rejection threshold incorrectly — using n instead of the largest multiple of n that fits within the source range, which silently reintroduces exactly the bias the rejection logic was supposed to eliminate.

Testing the Distribution of Generated Values

Verifying uniformity isn't optional if correctness genuinely matters for the use case — it has to be tested, not assumed. The standard approach is a chi-squared goodness-of-fit test: generate a large number of samples (tens of thousands at minimum for a small target range), bucket them by value, and compare the observed frequency in each bucket against the expected uniform frequency. A large chi-squared statistic relative to the target range's degrees of freedom indicates a distribution that's very unlikely to be uniform by chance.

For a quick sanity check rather than a formal test, simply generating a few hundred thousand samples and plotting a histogram will usually make anything but a very small bias visually obvious — the biased buckets in the worked example above, for instance, would show up as clearly taller bars than the others, well before you'd need a formal statistical test to confirm what the eye already suggests.