# Using the PCG C++ Implementation

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^{64}.

`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^{63} 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^{2112} period, in fact they each occur 2^{64} 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.

See also the page about party-trick generators.

## Available Generators

The library provides convenience typedefs to provide the following generators

### 32-Bit Generators with 64-Bit State

`pcg32`- 32-bit generator, 2
^{64}period, 2^{63}streams `pcg32_oneseq`- 32-bit generator, 2
^{64}period, one stream `pcg32_unique`- 32-bit generator, 2
^{64}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
^{62}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
^{128}period, 2^{127}streams `pcg64_oneseq`- 64-bit generator, 2
^{128}period, one stream `pcg64_unique`- 64-bit generator, 2
^{128}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
^{126}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
^{8}period, 2^{7}streams `pcg16_once_insecure`- 16-bit generator, 2
^{16}period, 2^{15}streams `pcg32_once_insecure`- 32-bit generator, 2
^{32}period, 2^{31}streams `pcg64_once_insecure`- 64-bit generator, 2
^{64}period, 2^{63}streams `pcg128_once_insecure`- 128-bit generator, 2
^{128}period, 2^{127}streams `pcg8_oneseq_once_insecure`- 8-bit generator, 2
^{8}period, one stream `pcg16_oneseq_once_insecure`- 16-bit generator, 2
^{16}period, one stream `pcg32_oneseq_once_insecure`- 32-bit generator, 2
^{32}period, one stream `pcg64_oneseq_once_insecure`- 64-bit generator, 2
^{64}period, one stream `pcg128_oneseq_once_insecure`- 128-bit generator, 2
^{128}period, one stream

### Extended 32-Bit Generators

`pcg32_k2`- 32-bit 2-dimensionally equidistributed generator, 2
^{128}period, 2^{63}streams `pcg32_k2_fast`- 32-bit 2-dimensionally equidistributed generator, 2
^{128}period, one stream `pcg32_k64`- 32-bit 64-dimensionally equidistributed generator, 2
^{2112}period, 2^{63}streams (about the same state size and period as`arc4random`) `pcg32_c64`- 32-bit generator, 2
^{2112}period, 2^{63}streams; uniform but not equidistributed; harder to predict than the above generator `pcg32_k1024`- 32-bit 64-dimensionally equidistributed generator, 2
^{32832}period, 2^{63}streams (larger period than the mersenne twister) `pcg32_c1024`- 32-bit generator, 2
^{32832}period, 2^{63}streams; uniform but not equidistributed; harder to predict than the above generator `pcg32_k16384`- 32-bit generator, 2
^{524352}period, 2^{63}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
^{2176}period, 2^{127}streams (about the same state size and period as`arc4random`) `pcg64_k64`- 64-bit generator, 2
^{2176}period, 2^{127}streams; uniform but not equidistributed; harder to predict than the above generator `pcg64_k1024`- 64-bit 64-dimensionally equidistributed generator, 2
^{65664}period, 2^{63}streams (larger period than the mersenne twister) `pcg32_c1024`- 64-bit generator, 2
^{65664}period, 2^{63}streams; uniform but not equidistributed; harder to predict than the above generator