When optimizing randomized algorithms, developers often focus intensely on selecting the fastest pseudorandom number generator (PRNG). Yet, as a revealing study inspired by Daniel Lemire’s research demonstrates, the real performance killer often lies elsewhere: in the deceptively simple task of generating numbers within a bounded range.

The Unseen Cost of Bounded Randomness

Most PRNGs output full machine words (e.g., 32 or 64 bits), but algorithms typically need numbers within specific ranges—like rolling dice (1-6) or selecting array indices. Converting raw random bits into these ranges introduces overhead, primarily due to expensive division operations and bias-correction logic. Common approaches include:

  1. Classic Modulo (% range): Simple but slow (division-heavy) and statistically biased.
  2. Floating-Point Multiply: Converts to FP, multiplies by range. Biased and non-portable.
  3. Integer Multiplication: Fixed-point alternative. Fast but biased.
  4. Rejection-Based Methods (e.g., OpenBSD, Java, Lemire): Unbiased but traditionally slower due to division/modulo checks.
  5. Bitmask with Rejection (Apple): Avoids division but may discard many values.
// Lemire's optimized unbiased method (fastest overall)
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
    uint32_t x = rng();
    uint64_t m = uint64_t(x) * uint64_t(range);
    uint32_t l = uint32_t(m);
    if (l < range) {
        uint32_t t = -range;
        if (t >= range) { t -= range; if (t >= range) t %= range; }
        while (l < t) { x = rng(); m = uint64_t(x)*range; l = uint32_t(m); }
    }
    return m >> 32;
}

Benchmarking the Real Impact

Rigorous testing across 23 methods, 26 PRNGs (including Mersenne Twister, JSF, PCG), and multiple compilers exposed dramatic performance differences:

  • Large-Shuffle Benchmark: Simulates shuffling massive arrays. Biased integer multiplication was fastest, but Lemire’s optimized method dominated unbiased techniques.

(Large-Shuffle Benchmark: Mersenne Twister)

  • All-Ranges Benchmark: Tests all possible range sizes. Bitmask rejection and Lemire’s method excelled, while modulo-based approaches lagged.

(All-Ranges Benchmark: Mersenne Twister)

  • Multi-PRNG Analysis: Faster PRNGs amplified differences in range-generation efficiency. Switching PRNGs offered ~45% speedups, but optimizing the range method delivered 66% reductions—tripling throughput.

(Large-Shuffle Benchmark: Multiple PRNGs)

Why This Matters

  1. Bias Isn’t Always Critical: For non-cryptographic use (e.g., Quicksort pivots), biased methods like integer multiplication suffice and maximize speed.
  2. Compiler Optimizations Help Constants: When ranges are compile-time constants, modulo and division methods improve but still trail multiplication.
  3. 64-bit ≠ Faster: Using 64-bit PRNGs for 32-bit ranges adds overhead without benefit.

The Verdict

While PRNG choice garners attention, neglecting range generation is like tuning an engine but ignoring the transmission. Lemire’s method with minor optimizations emerged as the fastest unbiased technique, often outperforming PRNG-switching by wide margins. As the opening anecdote of Huan (Mersenne Twister + fast scaling) beating Sasha (JSF + slow modulo) proves: how you constrain randomness frequently matters more than how you generate it.

Source: PCG Random Project, building on Daniel Lemire's work.