The PCG Paper

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.

Download and Read It

PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation

How to Cite It

If you'd like to cite the paper, here is a BibTeX entry.

@techreport{oneill:pcg2014,
    title = "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation",
    author = "Melissa E. O'Neill",
    institution = "Harvey Mudd College",
    address = "Claremont, CA",
    number = "HMC-CS-2014-0905",
    year = "2014",
    month = Sep,
    xurl = "https://www.cs.hmc.edu/tr/hmc-cs-2014-0905.pdf",
}

History

This paper was originally submitted to ACM Transactions on Mathematical Software (TOMS), but the reviewers would have preferred to have a paper that had far less review content. A much shorter paper might have been possible, but the review process took 320 days before any feedback was given. By that point, everyone who might have wanted to read it had almost certainly found it here and done so, so I saw little merit in drastically shortening the paper. A longer discussion of the history of the paper and the review process can be found in this blog post.

This page now links to the HMC-tech-report version of the paper, which is also available from my department's website. The content is the same as the version submitted to TOMS that was previously featured on this page, but the formatting is different (the TOMS version squeezes more content onto each page, so may be preferable if you're trying to save paper).

Errata

The PCG paper references a paper by Pierre L'Ecuyer, Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure, which lists constants for linear congruential generators. Apparently these constants were intended for uses such as Monte Carlo integration, rather than general-purpose random number generation. It is not clear to me how or why LCG constants with good lattice structure would be ill-suited for general-purpose random number generation, but L'Ecuyer has made the specific intent of the paper clear in his subsequent work. L'Ecuyer's paper also contains several errors which are corrected in an errata document available from his website. These issues make no difference whatsoever to the PCG family because every PCG generator permutes the output of the linear congruential generator it uses.

There are some modest aspects of the presentation that I might change if I were revising the paper. Most notably, I would

• Use the phrase “prediction difficulty” throughout in place of “cryptographic security” to make it even plainer than the paper already does that the PCG family is not intended for cryptographic use. I would emphasize more strongly why being predictable is a drawback and potential security issue for non-cryptographic use (i.e., algorithmic complexity attacks on randomized algorithms). Website content already adopts this renaming.
• Go into greater depth on how distinct additive constants for an LCG create multiple streams (the paper proves that all streams are distinct but fails to carefully note the ways in which two streams could be distinct but similar). This issue does not significantly diminish the value of streams for PCG, because PCG generators permute the output of the LCG.
• Use the term “output function” more often.
• Cite additional papers from the literature, including Parallel Random Numbers: As Easy as 1, 2, 3, by Salmon, Moraes, Dror, and Shaw.