Fast and reliable random number generators

Hans Dembinski

TU Dortmund

Take-home message

RIP Mersenne Twister, all hail to PCG
- Very fast and very small state (minimal version: 128 bits)
- Compact code
- Excellent randomness
- Seekable in O(1) time
- Can be made k-dimensionally equidistributed, like Mersenne Twister
- Open Source (Apache license)
- Default RNG in NumPy since 1.17
Use enough entropy to seed parallel-running RNGs
- Seeds need randomness ≈ size of RNG state
- In case of Mersenne Twister that is 20032 bits = 2.5 kB
- In case of PCG64, the seed size is 128 bits = 16 B
- Recommended: get seed from real entropy and save seed for reproducibility

PCG family: Better than your Dad’s RNG

PCG implementation

Solid mathematical foundation (see technical report for details)
- Combines non-trivial state-transition function with non-trivial output function
- Well-known idea: pass output of medium quality RNG to efficient hash function
Minimal PCG32 implementation in C

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

Full C++ implementation on Github: https://github.com/imneme/pcg-cpp

Performance

PCG64 passes TestU01 test suite with zero failures
Shown left are failures in Small crush and Big crush test batteries

PCG family is fastest among RNGs that pass statistical tests
PCG64 is twice as fast as Mersenne Twister which fails tests

And now for something completely different: Seeding

Naive seeding
- Initialise RNG with 32 or 64 bit integer
- At best: 2⁶⁴ independent streams of random numbers
Correct seeding
- Seed size ≈ RNG state
- Mersenne Twister has 2.5 kB state, difficult to seed!
- PCG64 requires only two int64_t

References

M.E. O’Neill, PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation, Tech. Rep. HMC-CS-2014-0905 (2014)
PCG homepage: https://www.pcg-random.org
NumPy Generator: https://numpy.org/doc/stable/reference/random/generator.html
TestU01: http://simul.iro.umontreal.ca/testu01/tu01.html
Wikipedia on Diehard tests: https://en.wikipedia.org/wiki/Diehard_tests