Using the PCG C++ Implementation

Contents

The C++ implementation provides the canonical reference implementation of the PCG family. It supports all family members, including extended generators, and offers the most flexibility. Despite its extreme flexibility, it's also easy to use. (If you'd like to look at code, however, you'd be better off starting with the minimal C library because that there is considerably less code.)

You can download the code from the download page.

Basics

You can use the PCG generation scheme exactly like other C++11-style generators (see, for example, Walter Brown's Random Number Generation in C++11 [PDF, WG21 N3551]).

Let's begin by taking some C++11 example code from cppreference.com, and then switching it over to the PCG scheme.

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>
#include <cmath>

int main()
{
    // Seed with a real random value, if available
    std::random_device rd;

    // Choose a random mean between 1 and 6
    std::default_random_engine e1(rd());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Randomly-chosen mean: " << mean << '\n';

    // Generate a normal distribution around that mean
    std::mt19937 e2(rd());
    std::normal_distribution<> normal_dist(mean, 2);

    // Produce histogram
    std::map<int, int> hist;
    for (int n = 0; n < 10000; ++n) {
        ++hist[std::round(normal_dist(e2))];
    }
    std::cout << "Normal distribution around " << mean << ":\n";
    for (auto p : hist) {
        std::cout << std::fixed << std::setprecision(1) << std::setw(2)
                  << p.first << ' ' << std::string(p.second/30, '*') << '\n';
    }
}

which produces output like this:

Randomly-chosen mean: 3
Normal distribution around 3:
-4
-3
-2 ***
-1 *********
 0 *********************
 1 ****************************************
 2 *********************************************************
 3 *******************************************************************
 4 ********************************************************
 5 *****************************************
 6 *********************
 7 **********
 8 ***
 9
10
11

We can switch this code over to PCG generation by adding #include "pcg_random.hpp" and using a PCG generator, such as pcg32 rather than std::default_random_engine and std::mt19937.

There is something worth noting about the above example code. Although it uses std::random_device for seeding, it initializes the generators with just one 32-bit random int from system's random device. In the case of std::mt19937, that's somewhat problematic because this generator uses 624 32-bit integers to provide 19937 bits of internal state, yet the code initializes it with a mere 32 bits of entropy. Why? Because C++11 (and C++14) makes proper initialization needlessly difficult. The PCG library makes it easier, providing seed_seq_from. The code below uses this feature, and some more features of the PCG library.

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>
#include <cmath>
#include "pcg_random.hpp"

int main()
{
    // Seed with a real random value, if available
    pcg_extras::seed_seq_from<std::random_device> seed_source;

    // Make a random number engine
    pcg32 rng(seed_source);

    // Choose a random mean between 1 and 6
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(rng);
    std::cout << "Randomly-chosen mean: " << mean << '\n';

    // Generate a normal distribution around that mean
    std::normal_distribution<> normal_dist(mean, 2);

    // Make a copy of the RNG state to use later
    pcg32 rng_checkpoint = rng;

    // Produce histogram
    std::map<int, int> hist;
    for (int n = 0; n < 10000; ++n) {
        ++hist[std::round(normal_dist(rng))];
    }
    std::cout << "Normal distribution around " << mean << ":\n";
    for (auto p : hist) {
        std::cout << std::fixed << std::setprecision(1) << std::setw(2)
                  << p.first << ' ' << std::string(p.second/30, '*') << '\n';
    }

    // Produce information about RNG usage
    std::cout << "Required " << (rng - rng_checkpoint) << " random numbers.\n";
}

Which produces output like this:

Randomly-chosen mean: 4
Normal distribution around 4:
-3
-2
-1 **
 0 *********
 1 **********************
 2 **************************************
 3 ************************************************************
 4 *****************************************************************
 5 **********************************************************
 6 *****************************************
 7 *********************
 8 *********
 9 ***
10
11
12
Required 25560 random numbers.

Notice that we've added a feature to the code. We can now determine how many random numbers std::normal_distribution needed to use from the base generator to produce normally distributed output. What's neat about this feature is that it didn't explicitly count how many times the generator was called, the difference is algorithmically determined by comparing the internal states of the two generators.

The above program runs quickly, but if we increase the constants, from 10,000 iterations and 30 numbers per star to 100,000,000 iterations and 300,000 per star, we can finally get a program that takes a noticeable time to run. It takes about 4.5 seconds on my laptop. In contrast, std::mt19937 requires 5.75 seconds (that's about 28% more time), and if we use std::minstd_rand instead, it takes 5.35 seconds (about 19% more time, despite being a statistically terrible generator).

And that shows you the essence of the C++ PCG generation library. It provides all the C++ generation facilities, plus some very handy extras. Plus, it's very fast, very space efficient and statistically excellent.

C++11 Standard Features

All the PCG generators provide the usual interface we'd expect for a random number generator. We'll use pcg32 as a running example, but these operations are supported by all PCG generators.

`result_type`

The integer type used for random values. pcg32::result_type is uint32_t.

`state_type`

The integer type used for the internal state of the generator. pcg32::state_type is uint64_t.

`pcg32::pcg32(...)` (constructor)

We support the following constructors:

pcg32(): default construct using a fixed seed (and a fixed stream)
explicit pcg32(state_type seed): construct with the given seed (and a fixed stream)
pcg32(state_type seed, state type stream): construct with the given seed and stream (only available on generators, such as pcg32, that support multiple streams); this is not a C++11 required feature
template <typename SeedSeq> pcg32(SeedSeq&& seq): initialize using the provided seed-sequence object
pcg32(const pcg32& orig): make a copy of orig

`void pcg32::seed(...)`

Reseed the generator. The arguments to the seed operation are identical to those passed to the constructor.

`result_type pcg32::operator()`

Advances the engine's state and a new pseudorandom value.

`void pcg32::discard(state_type n)`

Advances the engine's state by n. For all generators except non-equidistributed extended generators, it is a call to advance and takes O(log n) time.

`result_type pcg32::min()`

The least possible random value. Always returns zero.

`result_type pcg32::max()`

The greatest possible random value. Always returns the largest possible integer of result_type.

`bool operator==(const pcg32& lhs, const pcg32& rhs)`

Compare two RNG states for equality. Two generators are equal if they have the same state and represent the same random stream.

`bool operator!=(const pcg32& lhs, const pcg32& rhs)`

Opposite of operator==.

`std::ostream& operator<<(std::ostream& out, const pcg32& rng)`

Outputs the internal state to an ostream.

`std::istream& operator>>(std::istream& out, const pcg32& rng)`

Gets the internal state from an ostream.

Extra Features

`size_t period_pow2`

Returns the period of the generator as a power of two. For example, for pcg32, it returns 64, indicating a period of 2⁶⁴.

`result_type pcg32::operator()(result_type upper_bound)`

This function provides exactly the interface imagined by the designers of C++03's random_shuffle algorithm, it generates a random number n such that 0 <= n < upper_bound. In other words, it lets us write:

auto chosen_card = cards[rng(52)];

rather than

typedef std::uniform_int_distribution<rng::result_type> distribution_t;
distribution_t dist;
typedef typename distribution_t::param_type param_t;

auto chosen_card = cards[dist(g, param_t(0, 51))]

C++'s distribution classes are very-full featured, but for quick-and-simple programs, they often feel like overkill.

It also tends to be about twice as fast as GCC or Clang's implementation of std::uniform_int_distribution (which has to handle a wider variety of RNGs).

`void pcg32::set_stream(state_type stream)`

Allows you to choose the stream. It provides an alternative to passing the stream to the constructor or seed function (but the single-argument call to seed resets the stream to the default, so you would need to call set_stream after the call to seed).

`size_t streams_pow2`

Returns the number of streams as a power of two. For pcg32, it returns 63, indicating 2⁶³ streams.

`bool wrapped()`

Tells you when the RNG wraps around to the beginning (which we define as the zero state).

`void advance(state_type delta)`

Advances the generator forward delta steps, but does so in logarithmic time. (Not available for non-equidistributed extended generators.)

`void backstep(state_type delta)`

Move the generator backwards delta steps, but does so in logarithmic time. (Not available for non-equidistributed extended generators.)

`state_type operator-(const pcg32& lhs, const pcg32& rhs)`

Returns how much we would need to advance rhs for it to be equal to lhs. The generators must belong to the same stream.

This facility is not provided for the extended generators; a typical extended generator will have such a huge period that the delta would not fit in a simple variable.

Features for Extended Generators

We'll use pcg32_k64, a 64-dimensionally equidistributed generator, as our running example.

`state_type pcg32_k64::pcg32_k64(...)`

In addition to the usual constructors, extended generators also provide

explicit pcg32_k64(const result_type* data, state_type seed): construct with the given seed (and a fixed stream), initialize the extended data using the array data. For pcg32_k64, the array must hold 64 entries.
pcg32(const result_type* data, state_type seed, state type stream): as above, but construct with the given seed and stream (only available on generators, such as pcg32, that support multiple streams)

`void pcg32_k64::set(result_type desired)`

Adjust the generator state to create a new state that has just produced desired (yet leaving values within 63 either side of our position unaffected). This function allows you to create “party-trick” generators such as the one used in the code below.

#include <cstdio>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <sstream>
#include <string>
#include <random>

#include <unistd.h>

#include "pcg_random.hpp"

static const char* saved_state =
 "6364136223846793005 3503324247726078831 6557656048857751321 103238831 "
 "665891259 1902651333 4073047566 368781010 3371458373 3520911659 1176018374 "
 "1290944887 2479283234 2214499777 3287447736 4241043352 2808175048 83300271 "
 "162496091 3372211384 3773661488 3842517107 154403914 1983905875 185363760 "
 "3574548828 4259275054 2055322655 3183516320 3827707798 2358810643 3947601356 "
 "1518701804 2987610801 4256672123 243420444 2418646926 1593945712 3293969771 "
 "1047458160 4148325853 4134598831 813996594 2374617805 712898811 2110551176 "
 "233031372 1753202862 281911517 1950853967 3790278509 4176603202 4256155456 "
 "1413186342 1718872307 2898301505 1732438719 622306094 366401535 2963949396 "
 "2676833081 98878999 999895120 425860638 4096143638 4063627507 2566817785";


int main()
{
    pcg32_k64 rng;

    std::istringstream inbuf(saved_state);
    inbuf >> rng;
    if (inbuf.fail())
        abort();

    constexpr size_t BUFFER_SIZE = 1024ull * 128ull;
    uint32_t buffer[BUFFER_SIZE];
    constexpr size_t ROUNDS = 1024ull * 1024ull * 1024ull / sizeof(buffer);

    for (size_t i = 0; i < ROUNDS; ++i) {
        for (auto& v : buffer)
            v = rng();
        write(1, (void*) buffer, sizeof(buffer));
    }

    return 0;
}

It produces 1MB of random looking data, and then for just a short while, things get interesting. For example, here's part of the output:

001012f0  e6 55 40 70 ef 21 7b 9a  e7 1d 0e 3c 5b b7 3d b4  |.U@p.!{....<[.=.|
00101300  66 8c 36 b1 65 b7 e7 a7  3f 12 8c e2 1c 14 a8 52  |f.6.e...?......R|
00101310  b8 c8 84 15 43 3a bb 72  72 22 09 64 76 67 03 33  |....C:.rr".dvg.3|
00101320  c6 ff 4a 3d 2b 7e d4 17  11 d6 81 37 08 b7 1f 4a  |..J=+~.....7...J|
00101330  55 6e 6c 69 6b 65 6c 79  20 74 68 69 6e 67 73 20  |Unlikely things |
00101340  68 61 70 70 65 6e 2c 20  72 69 67 68 74 3f fe 83  |happen, right?..|
00101350  ed b3 4a 0d e2 ea f3 c1  70 a7 b6 8b db 5a d8 92  |..J.....p....Z..|
00101360  9b 1f 09 0f bf 12 6f 7a  46 8b 12 ba e1 1e a6 9e  |......ozF.......|
00101370  ef a9 0c ec dd 52 47 c5  82 26 a8 e8 d7 50 9a b9  |.....RG..&...P..|

Feel free to run the program, skip 1MB of output, and see what else you find.

It may seem strange to find some English text in the output of a random number generator, but that's what pcg32_k64's 64-dimensional equidistribution guarantees you—that every possible sequence of 64 32-bit values (i.e., 256 bytes) will occur in its staggering 2²¹¹² period, in fact they each occur 2⁶⁴ times. The only difficulty is finding such sequences in all the noise. The set operation means that you don't have to find such a state, you can create it.

Available Generators

The library provides convenience typedefs to provide the following generators

32-Bit Generators with 64-Bit State

pcg32: 32-bit generator, 2⁶⁴ period, 2⁶³ streams
pcg32_oneseq: 32-bit generator, 2⁶⁴ period, one stream
pcg32_unique: 32-bit generator, 2⁶⁴ period, every instance has its own unique stream (for I/O, you can output this generator and then read it back into a pcg32 generator)
pcg32_fast: 32-bit generator, 2⁶² period, one stream; faster but slightly less statistically good output function (nevertheless still very good)

64-Bit Generators with 128-Bit State

pcg64: 64-bit generator, 2¹²⁸ period, 2¹²⁷ streams
pcg64_oneseq: 64-bit generator, 2¹²⁸ period, one stream
pcg64_unique: 64-bit generator, 2¹²⁸ period, every instance has its own unique stream (for I/O, you can output this generator and then read it back into a pcg64 generator)
pcg64_fast`: 64-bit generator, 2¹²⁶ period, one stream

Insecure Generators

These generators only output each number exactly once during their period. They are compact, and are statistically excellent, but should not be used except in specialized scenarios.

pcg8_once_insecure: 8-bit generator, 2⁸ period, 2⁷ streams
pcg16_once_insecure: 16-bit generator, 2¹⁶ period, 2¹⁵ streams
pcg32_once_insecure: 32-bit generator, 2³² period, 2³¹ streams
pcg64_once_insecure: 64-bit generator, 2⁶⁴ period, 2⁶³ streams
pcg128_once_insecure: 128-bit generator, 2¹²⁸ period, 2¹²⁷ streams
pcg8_oneseq_once_insecure: 8-bit generator, 2⁸ period, one stream
pcg16_oneseq_once_insecure: 16-bit generator, 2¹⁶ period, one stream
pcg32_oneseq_once_insecure: 32-bit generator, 2³² period, one stream
pcg64_oneseq_once_insecure: 64-bit generator, 2⁶⁴ period, one stream
pcg128_oneseq_once_insecure: 128-bit generator, 2¹²⁸ period, one stream

Extended 32-Bit Generators

pcg32_k2: 32-bit 2-dimensionally equidistributed generator, 2¹²⁸ period, 2⁶³ streams
pcg32_k2_fast: 32-bit 2-dimensionally equidistributed generator, 2¹²⁸ period, one stream
pcg32_k64: 32-bit 64-dimensionally equidistributed generator, 2²¹¹² period, 2⁶³ streams (about the same state size and period as arc4random)
pcg32_c64: 32-bit generator, 2²¹¹² period, 2⁶³ streams; uniform but not equidistributed; harder to predict than the above generator
pcg32_k1024: 32-bit 64-dimensionally equidistributed generator, 2³²⁸³² period, 2⁶³ streams (larger period than the mersenne twister)
pcg32_c1024: 32-bit generator, 2³²⁸³² period, 2⁶³ streams; uniform but not equidistributed; harder to predict than the above generator
pcg32_k16384: 32-bit generator, 2⁵²⁴³⁵² period, 2⁶³ streams; useful for extreme party tricks

Extended 64-Bit Generators

These generators are not currently supported on machines without native 128-bit math. (Adding support requires C++14's enhanced constexpr features.).

pcg64_k32: 64-bit 32-dimensionally equidistributed generator, 2²¹⁷⁶ period, 2¹²⁷ streams (about the same state size and period as arc4random)
pcg64_k64: 64-bit generator, 2²¹⁷⁶ period, 2¹²⁷ streams; uniform but not equidistributed; harder to predict than the above generator
pcg64_k1024: 64-bit 64-dimensionally equidistributed generator, 2⁶⁵⁶⁶⁴ period, 2⁶³ streams (larger period than the mersenne twister)
pcg32_c1024: 64-bit generator, 2⁶⁵⁶⁶⁴ period, 2⁶³ streams; uniform but not equidistributed; harder to predict than the above generator