This repository contains implementations in C of the preferred 32-bit and 64-bit variants of Melissa O'Neill's PCG family of random number algorithms, with Daniel Lemire's nearly-divisionless algorithm for unbiased bounded random numbers, and functions for random floating point numbers.
The PCG functions are constructed from a collection of linear congruential generators and a collection of output permutations.
A linear congruential random number generator looks like:
state = state * mul + inc;
The multiplier mul is usually fixed; the increment inc can be
fixed, but PCG implementations usually allow it to be chosen when the
RNG is seeded.
A bare LCG is a bad RNG. PCG turns an LCG into a good RNG:
- The LCG state is twice the size of the RNG output
- The LCG state is permuted to produce the RNG output
The reference implementation of PCG in C++ allows you to mix and match LCGs and output permutations at a variety of integer sizes. My implementation provides just one 32-bit RNG and one 64-bit RNG.
The file pcg32_xsh_rr.c contains the preferred 32-bit variant of
PCG. The output permutation's name "XSH RR" is short for "xor shift
rotate right".
In C++ PCG this variant is called
pcg_engines::setseq_xsh_rr_64_32 or simply pcg32 for short.
It is the only variant provided by the basic C PCG.
The file pcg64_dxsm.c contains the preferred 64-bit variant of PCG.
It is harder to find out about it on the PCG web site, though
it is increasingly popular. Melissa O'Neill describes
it as follows:
DXSM -- double xor shift multiply
This is a new, more powerful output permutation (added in 2019). It's a more comprehensive scrambling than RXS M, but runs faster on 128-bit types. Although primarily intended for use at large sizes, also works at smaller sizes as well.
O'Neill wrote a longer description of the design of pcg64_dxsm elsewhere.
As well as the DXSM output permutation, this pcg64 variant uses a
"cheap multiplier", i.e. a 64-bit value half the width of the state,
instead of a 128-bit value the same width as the state. The same
multiplier is used for the LCG and the output permutation.
In C++ PCG its full name is pcg_engines::cm_setseq_dxsm_128_64.
(The C++ PCG typedef pcg64 still refers to the previously preferred
xsl_rr variant.)
Random numbers up to some limit are generated by pcg32_rand() and
pcg64_rand() using Daniel Lemire's nearly-divisionless unbiased
rejection sampling algorithm for bounded random
numbers. In this implementation the algorithm is split
into an inline fast path and a separate slow path.
Arcane tricks are used to completely omit the slow path when possible.
The expression limit & limit - 1 is zero when the limit is a power
of two or zero; when it is cast to void * it is either a null
pointer constant (always fast) or not (maybe slow). The type of a ?:
expression with a void * branch and another pointer branch is
usually void *, unless the void * is a null pointer constant, in
which case the ?: type is the other pointer type. A _Generic()
expression can turn the type of the ?: into a boolean value
indicating whether the limit is always fast or maybe slow.
There are also pcg32_random_float() and pcg64_random_double()
functions that generate random numbers in 0.0 <= ... < 1.0 using
shift-cast-and-multiply.
Type make.
The files pcg{32,64}.[ch] are generated. They are designed to be
self-contained so that you can copy them into your own projects.
The files pcg32_xsh_rr.c and pcg64_dxsm.c contain the
size-specific algorithms for generating random integer and floating
point values.
The files pcg.[ch] contain code that is generic over the bit size:
- the RNG state type
- seeding the RNG
- Lemire's algorithm
The files pcg{32,64}.def contain macros to configure the generic
code for 32 bits and 64 bits, respectively. The files pcg_blurb.[ch]
are the prefixes of the generated files.
The file shuffle.c contains a Fisher-Yates shuffle using pcg32 and
Lemire's algorithm. Internally it uses pcg64 to shuffle very large
arrays.
Written by Tony Finch <[email protected]> in Cambridge.
Permission is hereby granted to use, copy, modify, and/or
distribute this software for any purpose with or without fee.
This software is provided 'as is', without warranty of any kind.
In no event shall the authors be liable for any damages arising
from the use of this software.
SPDX-License-Identifier: 0BSD OR MIT-0