Using the Full C Implementation
The full C implementation provides many members of the PCG family, allowing far greater flexibility compared to the minimal C library, and provides some additional features, including jump-ahead/jump-back.
The code is also written so as to allow the compiler to inline RNG calls, resulting in faster execution.
The interface is similar to the Unix rand/rand_r and random/random_r interfaces. See the minimal C library for a basic description.
Playing with the Code
If you've not done so already download the code and build it running:
make make test
You can then run one of the sample programs from the sample directory, such as pcg32-demo. If you run it, it should produce the following output (always the same, because it uses a fixed seed—invoke it with -r if you want different output each time):
pcg32_random_r: - result: 32-bit unsigned int (uint32_t) - period: 2^64 (* 2^63 streams) - state type: pcg32_random_t (16 bytes) - output func: XSH-RR Round 1: 32bit: 0xa15c02b7 0x7b47f409 0xba1d3330 0x83d2f293 0xbfa4784b 0xcbed606e Again: 0xa15c02b7 0x7b47f409 0xba1d3330 0x83d2f293 0xbfa4784b 0xcbed606e Coins: HHTTTHTHHHTHTTTHHHHHTTTHHHTHTHTHTTHTTTHHHHHHTTTTHHTTTTTHTTTTTTTHT Rolls: 3 4 1 1 2 2 3 2 4 3 2 4 3 3 5 2 3 1 3 1 5 1 4 1 5 6 4 6 6 2 6 3 3 Cards: Qd Ks 6d 3s 3d 4c 3h Td Kc 5c Jh Kd Jd As 4s 4h Ad Th Ac Jc 7s Qs 2s 7h Kh 2d 6c Ah 4d Qh 9h 6s 5s 2c 9c Ts 8d 9s 3c 8c Js 5d 2h 6h 7d 8s 9d 5h 8h Qc 7c Tc ⋮ ⋮ Round 5: 32bit: 0xfcef7cd6 0x1b488b5a 0xd0daf7ea 0x1d9a70f7 0x241a37cf 0x9a3857b7 Again: 0xfcef7cd6 0x1b488b5a 0xd0daf7ea 0x1d9a70f7 0x241a37cf 0x9a3857b7 Coins: HHHHTHHTTHTTHHHTTTHHTHTHTTTTHTTHTHTTTHHHTHTHTTHTTHTHHTHTHHHTHTHTT Rolls: 5 4 1 2 6 1 3 1 5 6 3 6 2 1 4 4 5 2 1 5 6 5 6 4 4 4 5 2 6 4 3 5 6 Cards: 4d 9s Qc 9h As Qs 7s 4c Kd 6h 6s 2c 8c 5d 7h 5h Jc 3s 7c Jh Js Ks Tc Jd Kc Th 3h Ts Qh Ad Td 3c Ah 2d 3d 5c Ac 8s 5s 9c 2h 6c 6d Kh Qd 8d 7d 2s 8h 4h 9d 4s
This example code shows some common RNG use cases; it
- Prints out some 32-bit random numbers
- Uses the jump-back facility to repeat those same numbers again
- Tosses some coins (i.e., performs a binary choice)
- Rolls some dice (i.e., produces numbers in the range 1-6, without introducing bias or destroying uniformity)
- Shuffles and deals some playing cards
Looking at the code ought to tell you a lot about using the library.
Basic High Level API
First, we'll cover the using the pcg32 generator from the high-level API (which is almost identical to the version provided by the minimal C library, except that it also provides pcg32_advance, see below).
Internally, this RNG uses two 64-bit integers for its internal state, consisting of:
- the current state — the RNG iterates through all 2^{64} possible internal states.
- the RNG-sequence constant — a value that defines which of 2^{63} possible random sequences the current state is iterating through; it holds the same value over the lifetime of the RNG.
Different values for sequence constant cause the generator to produce a different (and unique) sequence of random numbers (sometimes called the stream). In other words, it's as if you have 2^{63} different RNGs available, and this constant lets you choose which one you're using.
You can create as many separate RNGs as you like. If you give them different sequence constants, they will be independent and uncorrelated with each other (i.e., their sequences will not overlap at all).
As a convenience, the pcg32 scheme also provides a global RNG. (No attempt is made to arbitrate access to this global; state—multithreaded programs should either perform their own locking, or, far more sensibly, provided each thread with its own, independent, RNG.)
The API centers around these functions:
void pcg32_srandom_r(pcg32_random_t* rngptr, uint64_t initstate, uint64_t initseq) uint32_t pcg32_random_r(pcg32_random_t* rngptr) uint32_t pcg32_boundedrand_r(pcg32_random_t* rngptr, uint32_t bound) void pcg32_advance_r(pcg32_random_t* rngptr, uint64_t delta)
and these variants for the global RNG:
void pcg32_srandom(uint64_t initstate, uint64_t initseq) uint32_t pcg32_random() uint32_t pcg32_boundedrand(uint32_t bound) void pcg32_advance(uint64_t delta)
These functions, and the pcg32_random_t type, are declared by
#include <pcg_variants.h>
You will also need to link your code with the libpcg_random library.
pcg32_srandom_r(rngptr, initstate, initseq)
This function initializes (a.k.a. “seeds”) the random number generator, a required initialization step before the generator can be used. The provided arguments are defined as follows:
- rngptr should point to the address of a pcg32_random_t value that you've previously declared
- initstate is the starting state for the RNG, you can pass any 64-bit value.
- initseq selects the output sequence for the RNG, you can pass any 64-bit value, although only the low 63 bits are significant.
For this generator, there are 2^{63} possible sequences of pseudorandom numbers. Each sequence is entirely distinct and has a period of 2^{64}. The initseq argument selects which stream you will use. The initstate argument specifies where you are in that 2^{64} period.
Calling pcg32_srandom_r with the same arguments produces the same output, allowing programs to use random number sequences repeatably.
If you want truly nondeterministic output for each run of your program, you should pass values that will be different from run to run. On a Unix system, /dev/random provides random bytes that can be used for initialization (the full C library provides a handy wrapper function entropy_getbytes to help), but if you want a quick and dirty way to do the initialization, one option is to pass the current time and the address of the RNG itself.
For example, this code initializes three RNGs, and they really do produce different values even though the time probably doesn't advance between calls.
pcg32_random_t rng1, rng2, rng3; pcg32_srandom_r(&rng1, time(NULL), (intptr_t)&rng1); pcg32_srandom_r(&rng2, time(NULL), (intptr_t)&rng2); pcg32_srandom_r(&rng3, time(NULL), (intptr_t)&rng3);
(See also pcg32u_random_t, described below, which always use the address of the RNG for the current stream, reducing the space usage for the RNG state by half.)
The function pcg32_srandom(initstate, initseq) behaves identically, but uses the global RNG.
Failing to correctly initialize the state can result in a generator with improper behavior (for example, all-zeros initialization will produce a generator that always returns zero). If for some reason you cannot call pcg32_srandom_r, you can initialize a variable using the special constant PCG32_INITIALIZER which expands a standard C brace-initialization constant with some suitably chosen fixed constants. The global generator is suitably initialized in this way so that it will work even without a call to pcg32_srandom (although it will always produce the same pseudorandom sequence).
pcg32_random_r(rngptr)
Generates a pseudorandom uniformly distributed 32-bit unsigned integer (i.e., x where, 0 <= x < 2^{32}).
The function pcg32_random() behaves identically, but uses the global RNG.
pcg32_boundedrand_r(rngptr, bound)
Generates a uniformly distributed 32-bit unsigned integer less than bound (i.e., x where 0 <= x < bound).
Some programmers may think that they can just run pcg32_random_r(rng) % bound, but doing so introduces nonuniformity when bound is not a power of two. The code for pcg32_boundedrand_r avoids the nonuniformity by dropping a portion of the RNG's output.
The function pcg32_boundedrand(bound) behaves identically, but uses the global RNG.
pcg32_advance_r(rngptr, delta)
This operation provides jump-ahead; it advances the RNG by delta steps, doing so in log(delta) time. Because of the periodic nature of generation, advancing by 2^{64} - d (i.e., passing -d) is equivalent to backstepping the generator by d steps.
Note that a call to pcg32_random_r coundt as one step, whereas calls to pcg32_boundedrand_r can require multiple steps because it can discard some outputs.
Generating doubles
Like the Unix rand and random facilites, this library does not provide a direct facility to generate floating point random numbers. It turns out that generating random floating point values is surprisingly challenging. If you are happy to have a floating point value in the range [0,1) that has been rounded down to the nearest multiple of 1/2^{32}, you can use
double d = ldexp(pcg32_random_r(&myrng), -32);
(Or, you can analogously use a 64-bit generator if 32-bits of resolution are not enough.)
Other High-Level API Types
In addition to pcg32_random_t, the high-level API provides several other types, specifically
Type Name | Output Type | Seed Type | Bytes | Period & Streams |
---|---|---|---|---|
pcg32_random_t | uint32_t | uint64_t | 16 | 2^{64} × 2^{63} streams |
pcg32s_random_t | uint32_t | uint64_t | 8 | 2^{64} |
pcg32u_random_t | uint32_t | uint64_t | 8 | 2^{64} × #rngs |
pcg32f_random_t | uint32_t | uint64_t | 8 | 2^{62} |
pcg64_random_t | uint64_t | pcg128_t | 32 | 2^{128} × 2^{127} streams |
pcg64s_random_t | uint64_t | pcg128_t | 16 | 2^{128} |
pcg64u_random_t | uint64_t | pcg128_t | 16 | 2^{128} × #rngs |
pcg64f_random_t | uint64_t | pcg128_t | 16 | 2^{126} |
The generation schemes are available at two different sizes, 32-bit output (which is suffficient for most purposes), and a 64-bit output scheme. The 64-bit scheme is only supported on platforms that support 128-bit integers (e.g., using GCC or Clang as the compiler on a 64-bit system).
There are also variations depending on whether or not you want different random number generators to have their own distinct streams. The meanings of the suffixes are described below
- No suffix (e.g., pcg32…), provide multiple streams. The user can select any of the possible output sequences.
- s suffix (e.g., pcg32s…), provide a single stream. There is just one output sequence. Given the large period, if multiple RNGs are initialized properly, it is unlikely that the outputs will ever coincide. This is especially true for the 64-bit output versions.
- u suffix (e.g., pcg32u…), provide a unique stream. Each RNG of this type is guaranteed to have a different output sequence from all others. Internally, it uses the memory address of the state to determine the sequence. Because most modern operating systems use ASLR, memory layout can and will vary from run to run, meaning that different runs of the program may produce different sequences.
- f suffix (e.g., pcg32u…), be as fast as possible; provide a single stream, a smaller period, and possibly a statistically weaker (but nevertheless good) output function.
Specialized Generators
The high-level API also provides some specialized generators. The i suffix stands for both the roman numeral for 1 and for insecure; because they produce each output exactly once, and as a result, they can offer no security—they reveal their entire internal state with each output. Do not use these generators unless you fully understand the ramifications of these properties.
As above, the s suffix versions provide a single stream.
The 8-bit and 16-bit variants obviously have a very small period and are ill-suited for general-purpose use (they can, however, be interesting for exploring how the generation schemes behave).
Type Name | Output Type | Seed Type | Bytes | Period & Streams |
---|---|---|---|---|
pcg8i_random_t | uint8_t | uint8_t | 2 | 2^{8} × 2^{7} streams |
pcg16i_random_t | uint16_t | uint16_t | 4 | 2^{16} × 2^{15} streams |
pcg32i_random_t | uint32_t | uint32_t | 8 | 2^{32} × 2^{31} streams |
pcg64i_random_t | uint64_t | uint64_t | 16 | 2^{64} × 2^{63} streams |
pcg128i_random_t | pcg128_t | pcg128_t | 32 | 2^{128} × 2^{127} streams |
pcg8si_random_t | uint8_t | uint8_t | 1 | 2^{8} |
pcg16si_random_t | uint16_t | uint16_t | 2 | 2^{16} |
pcg32si_random_t | uint32_t | uint32_t | 4 | 2^{32} |
pcg64si_random_t | uint64_t | uint64_t | 8 | 2^{64} |
pcg128si_random_t | pcg128_t | pcg128_t | 16 | 2^{128} |
Low-Level API
The low level API provides access to a proader range of the PCG family. For completeness, here is a list of all the low-level generators:
pcg_oneseq_8_rxs_m_xs_8_random_r pcg_setseq_8_rxs_m_xs_8_random_r pcg_mcg_16_xsh_rr_8_random_r pcg_mcg_16_xsh_rs_8_random_r pcg_oneseq_16_rxs_m_xs_16_random_r pcg_oneseq_16_xsh_rr_8_random_r pcg_oneseq_16_xsh_rs_8_random_r pcg_setseq_16_rxs_m_xs_16_random_r pcg_setseq_16_xsh_rr_8_random_r pcg_setseq_16_xsh_rs_8_random_r pcg_unique_16_rxs_m_xs_16_random_r pcg_unique_16_xsh_rr_8_random_r pcg_unique_16_xsh_rs_8_random_r pcg_mcg_32_xsh_rr_16_random_r pcg_mcg_32_xsh_rs_16_random_r pcg_oneseq_32_rxs_m_xs_32_random_r pcg_oneseq_32_xsh_rr_16_random_r pcg_oneseq_32_xsh_rs_16_random_r pcg_setseq_32_rxs_m_xs_32_random_r pcg_setseq_32_xsh_rr_16_random_r pcg_setseq_32_xsh_rs_16_random_r pcg_unique_32_rxs_m_xs_32_random_r pcg_unique_32_xsh_rr_16_random_r pcg_unique_32_xsh_rs_16_random_r pcg_mcg_64_xsh_rr_32_random_r pcg_mcg_64_xsh_rs_32_random_r pcg_mcg_64_xsl_rr_32_random_r pcg_oneseq_64_rxs_m_xs_64_random_r pcg_oneseq_64_xsh_rr_32_random_r pcg_oneseq_64_xsh_rs_32_random_r pcg_oneseq_64_xsl_rr_32_random_r pcg_oneseq_64_xsl_rr_rr_64_random_r pcg_setseq_64_rxs_m_xs_64_random_r pcg_setseq_64_xsh_rr_32_random_r pcg_setseq_64_xsh_rs_32_random_r pcg_setseq_64_xsl_rr_32_random_r pcg_setseq_64_xsl_rr_rr_64_random_r pcg_unique_64_rxs_m_xs_64_random_r pcg_unique_64_xsh_rr_32_random_r pcg_unique_64_xsh_rs_32_random_r pcg_unique_64_xsl_rr_32_random_r pcg_unique_64_xsl_rr_rr_64_random_r pcg_mcg_128_xsh_rr_64_random_r pcg_mcg_128_xsh_rs_64_random_r pcg_mcg_128_xsl_rr_64_random_r pcg_oneseq_128_rxs_m_xs_128_random_r pcg_oneseq_128_xsh_rr_64_random_r pcg_oneseq_128_xsh_rs_64_random_r pcg_oneseq_128_xsl_rr_64_random_r pcg_oneseq_128_xsl_rr_rr_128_random_r pcg_setseq_128_rxs_m_xs_128_random_r pcg_setseq_128_xsh_rr_64_random_r pcg_setseq_128_xsh_rs_64_random_r pcg_setseq_128_xsl_rr_64_random_r pcg_setseq_128_xsl_rr_rr_128_random_r pcg_unique_128_rxs_m_xs_128_random_r pcg_unique_128_xsh_rr_64_random_r pcg_unique_128_xsh_rs_64_random_r pcg_unique_128_xsl_rr_64_random_r pcg_unique_128_xsl_rr_rr_128_random_r
The naming scheme is pcg_ stream-scheme _ lcg-size _ output-function output-size. For more details, see the code.
The high-level API just consists of typedefs and #defines that map to functions in the low-level API.