The PCG Paper

Although this website gives you a taste of what the PCG family is and can do, the technical details are given in the paper, PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. This paper is currently submitted to ACM Transactions on Mathematical Software, where it is currently under review.

What's in the Paper

Although it includes technical details, the paper is written to be accessible to a broad audience.

The paper

  • Articulates in detail the desirable properties of a random number generator including performance, correctness, uniformity, and unpredictability, as well as sound mathematical grounding. It also describes some less well-known desirable features, such as k-dimensional equidistribution and seekability (a.k.a. jump-ahead).
  • Describes a new permutation technique, founded on the idea of permutation functions on tuples, that can dramatically improve the output quality of a medium-quality random number generator while preserving important qualities such as uniformity.
  • Develops a new random number generation technique, using a base RNG with weak statistical properties but other desirable ones (specifically, a linear congruential generator) combined with an output function based on permutation functions on tuples.

The name for the family, PCG, stands for permuted congruential generator, combining both concepts that underly the generation scheme, namely permutation functions on tuples and a base linear congruential generator.

In addition to describing the PCG family, the paper also assesses its performance. To further that goal, the paper

  • Develops a model for the performance of an ideal uniform random number generator with b bits of state, including the notion of the point at which such a generator becomes overtaxed and the constraints of uniformity make it unable to deliver truly random behavior.
  • Determines an approximation of the point at which any uniform generator, even an ideal one, could be expected to fail TestU01's statistical tests.
  • Presents a new way to contrast the statistical performance of different random number generation schemes capturing the concept of headroom to pass more stringent tests in the future.
  • Uses the above statistical-performance comparison scheme, as well as time and space performance, to contrast PCG generators with existing ones.