Useful Features

On this page, we'll examine a number of useful features a random-number generator ought to have. The discussion will assume you're familiar with the basics of pseudorandom number generation.

Easy Seeding

If you want your random number to produce random numbers that can't be easily predicted, you need to use an external source of randomness to kickstart the process. Many random number libraries utterly fail the programmer in this regard, leaving it up to them to figure out how to seed it using external randomness. This approach leaves programmers resorting to weak-but-easy methods.

In contrast, the C++ PCG library provides some extras to make this task easy. You can declare and randomly initialize a PCG-32 generator:

pcg_extras::seed_seq_from<std::random_device> myExternalRandomness;
pcg32 myRNG(myExternalRandomness);

This technique works for other C++ generators, such as the Mersenne Twister. For the PCG family, we can be briefer and write it as:

pcg32 myRNG(seed_seq_from<std::random_device>{});

If you're writing a quick program and you're okay with lower quality seeding but you would like your program to “have different random numbers every time”, you can actually just write:

pcg32_unique myRNG;

(This last one relies on the operating system placing myRNG at a different address every time the program is run. It's not as strong as the other techniques.)

Multiple Streams/Sequences

As we discussed in basics of pseudorandom number generation, having a generator that provides N different streams is like having N distinct generators. For example, we can create a 64-bit generator out of two 32-bit generators that use distinct streams. In the PCG generation scheme, code to do so would look like this:

pcg32  low32rng(42 /* seed */, 1 /* stream #1 */);
pcg32 high32rng(42 /* seed */, 2 /* stream #2 */);

Even though both RNGs are seeded with 42, they produce completely different output that will never overlap.

Jump-Ahead and Jump-Back

As we discussed in basics of pseudorandom number generation, a random number generator is like a book that lists page after page of statistically random numbers. The seed gives us a starting point, but sometimes it is useful to be able to move forward or backwards in the sequence, and to be able to do so efficiently.

The C++ implementation of the PCG generation scheme provides advance to efficiently jump forwards and backstep to efficiently jump backwards.

Distance

If two variables hold generators belonging to the same stream, there is some amount we could advance one to reach the other. A distance function lets us calculate how far they are apart.

Here's a use case:

pcg32 myRNG(seed_seq_from<std::random_device>{});

foo(myRNG);         // Do some stuff...

pcg32 myRNGcheckpoint = myRNG;

bar(myRNG)          // Do more stuff...

size_t randomNumbersUsedByBar = myRNG - myRNGcheckpoint;

In this code, randomNumbersUsedByBar tells us how many random numbers were used by the bar function.

The C++ implementation of the PCG generation scheme provides this operation.

K-Dimensional Equidistribution

Sometimes we want to use a random number generator to produce not just numbers but pairs of numbers, or perhaps k-tuples for some k. We might want to be sure that every possible k-tuple will appear. We might even want to be sure that there is no systemic bias towards any particular k-tuple. If a generator is k-dimensionally equidistributed, it guarantees that over the full period of the generator, every k-tuple will appear the same number of times.

The C++ implementation of PCG family includes extended generators that provide k dimensional equidistribution for arbitrary k.

Party Tricks

They say that an infinite number of monkeys at an infinite number of typewriters will produce all the works of Shakespeare. If we use a k-dimensionally distributed generator with a large enough k, we know that all the works of Shakespeare are guaranteed to be produced eventually, it will just take an unimaginable amount of time to find them.

But that's assuming we search blindly. We can instead contrive the state of the generator so that it will find them, thus creating a party trick. We set up the generator so that it will find a Shakespeare play, and then jump backwards from that point, creating a generator that produces millions or billions of random-looking numbers, and then, suddenly, a Shakespeare play, and then back to random numbers.

The extended generators provided by the C++ implementation of PCG family include a set function that can be used to create party trick generators, including ones that really do output Shakespeare.

I/O

It's nice if we can serialize RNG state to a file and then read it back later. All C++ generators provide this facility.