What version of Effect is running?

3.21.0

Description

PCGRandom.integer() in packages/effect/src/Utils.ts uses Math.round(this.number() * Number.MAX_SAFE_INTEGER) % max, which introduces two distinct sources of statistical bias that deviate from the PCG reference implementation.

Reproduction

Location

File: packages/effect/src/Utils.ts
Lines: 612–615 (approximate)

/**
 * Get a uniformly distributed 32 bit integer between [0, max).
 *
 * @category getter
 * @since 2.0.0
 */
integer(max: number) {
  return Math.round(this.number() * Number.MAX_SAFE_INTEGER) % max
}

Consumed by: packages/effect/src/internal/random.ts, line 50

nextIntBetween(min: number, max: number): Effect.Effect<number> {
  return core.sync(() => this.PRNG.integer(max - min) + min)
}

Issue 1: Math.round() bias

Math.round() creates systematic non-uniformity. For any continuous range mapped to discrete integers, the first and last values receive half the probability mass of interior values:

this.number() returns [0, 1)

Mapping to [0, 99] via Math.round(n * MAX_SAFE_INTEGER) % 99:

[0.0, 0.5)      → 0   (width: 0.5)
[0.5, 1.5)      → 1   (width: 1.0)
[1.5, 2.5)      → 2   (width: 1.0)
...
[98.5, 99.0)    → 99  (width: 0.5)  ← half probability!

The MDN documentation explicitly warns against using Math.round() for random integer generation:

"Using Math.round() will give you a non-uniform distribution!"
— MDN: Math.random()

Issue 2: Modulo bias

Number.MAX_SAFE_INTEGER = 2^53 - 1 = 9,007,199,254,740,991 is not evenly divisible by most values of max.

For max = 99:

MAX_SAFE_INTEGER % 99 = 40

This means raw values 0 through 40 get one extra hit in the modulo cycle. Values 0–40 are overrepresented; values 41–98 are underrepresented.

"Although this approach [modulo] is simple, it is also biased... For a 32-bit PRNG, a bounded range of less than 2^24 has a bias of less than 0.5% but above 2^31 the bias is 50%—some numbers will occur half as often as others."
— PCG Blog: Bounded Rands

Issue 3: Double state consumption

number() calls _next() twice per value to construct a 53-bit float:

number() {
  const hi = (this._next() & 0x03ffffff) * 1.0  // consumes 1 state advance
  const lo = (this._next() & 0x07ffffff) * 1.0  // consumes 1 state advance
  return (hi * BIT_27 + lo) / BIT_53
}

The PRNG state advances 2× per integer when only 1× is needed. This is inefficient and advances the generator faster than necessary.

Expected Behavior

integer(max) should produce a uniformly distributed integer in [0, max) with no bias.

Reference Implementation

The official C++ PCG reference library (pcg-cpp) uses rejection sampling (OpenBSD arc4random_uniform style):

// pcg-cpp/include/pcg_extras.hpp (lines 540–552)
template <typename RngType>
auto bounded_rand(RngType& rng, typename RngType::result_type upper_bound)
        -> typename RngType::result_type
{
    typedef typename RngType::result_type rtype;
    rtype threshold = (RngType::max() - RngType::min() + rtype(1) - upper_bound)
                    % upper_bound;
    for (;;) {
        rtype r = rng() - RngType::min();
        if (r >= threshold)
            return r % upper_bound;
    }
}

The original JavaScript pcg-random library (which Effect-TS adapted from) also intended to use rejection sampling:

// Original pcg-random intention (Thom Chiovoloni)
var skew = ((-max >>> 0) % max) >>> 0
for (num = this.next32(); num < skew; num = this.next32()) {
  // rejection sampling
}
return num % max

Proposed Fix

Replace the biased floating-point approach with rejection sampling on raw 32-bit output:

integer(max: number): number {
  if (max <= 0) {
    throw new Error("max must be positive")
  }

  // For max that evenly divides 2^32, no rejection needed
  if ((0x100000000 % max) === 0) {
    return this._next() % max
  }

  // Rejection sampling to eliminate modulo bias
  const threshold = ((-max >>> 0) % max) >>> 0
  let result: number
  do {
    result = this._next() >>> 0
  } while (result < threshold)

  return result % max
}

This fix:

1. Eliminates Math.round() bias entirely
2. Eliminates modulo bias via rejection sampling
3. Consumes only one _next() call per integer (efficient)
4. Matches the official PCG C++ reference implementation

Impact

Any code using Random.nextIntBetween(min, max) or Random.nextInt is affected. This includes:

• Random.shuffle() — shuffles may be biased
• Random.choice() — selection may favor certain elements
• User code calling nextIntBetween directly

The bias is small for large ranges but becomes significant for small ranges (e.g., max = 2, max = 99), where it can reach several percent.

Environment

• effect version: All versions with current PCGRandom.integer() implementation
• File: packages/effect/src/Utils.ts
• Related: packages/effect/src/internal/random.ts

Additional Context

• PCG Blog: Bounded Rands — detailed explanation of modulo bias and rejection sampling
• MDN: Math.random() — warning against Math.round()
• OpenBSD arc4random_uniform — reference rejection sampling implementation
• pcg-cpp reference implementation — official C++ PCG bounded random