#051 - Introduction to random number generation in C++

An application might need to generate random numbers for various reasons. Calculating damage in games, statistical modelling and cryptography. Unfortunately, computers are incapable of generating truly random numbers, since their designed to be deterministic. Thus, a contradiction appears.

The workaround is we can simulate randomness by using an algorithm.

Let’s get started shall we.

A PRNG algorithm

To generate random numbers, we can use a Pseudo-Random Number Generator (PRNG) algorithm.

#include <iostream>

unsigned int myPRNG() // our PRNG
{
    static unsigned int s_state{ 0 }; 

    // Generate the next number by randomnly modifying it,
    // Making it difficult for someone to guess
    s_state = 8773729 * s_state + 3396403; 
    return s_state % 32128; 
}

int main()
{
    // Print 100 random numbers
    for (int count{ 1 }; count <= 25; ++count)
    {
        std::cout << myPRNG() << '\t';

        // Format the results
        if (count % 5 == 0)
            std::cout << '\n';
    }
}
// Terminal
22963   28678   22009   8844    31423
7442    19717   7832    23499   32030
4881    23332   14935   42      18205
2480    24803   22710   11049   14396
19055   16066   14133   456     15355

Awesome!

Let’s do that again.

// 2nd generation
22963   28678   22009   8844    31423
7442    19717   7832    23499   32030
4881    23332   14935   42      18205
2480    24803   22710   11049   14396
19055   16066   14133   456     15355

?? The program generated the exact same supposedly ‘random’ numbers.

What’s going on?

This is not a bug. The algorithm is deterministic and the initial state is fixed at zero, so the sequence is fully determined before the program even starts. What we need to do is seed the PRNG algorithm.

Seeding a PRNG

The issue is that the initial state of the program is fixed across program executions. We can alter the initial state or seed of our program by seeding the PRNG algorithm. This allows us to generate unique random numbers on each program execution.

The program below prompts the user for a seed value

#include <iostream>
#include <random>

static unsigned int s_state{ 0 };

void seedMyPRNG(int sVal) {
    s_state = sVal;
}

unsigned int myPRNG() 
{

    // Generate the next number by randomnly modifying it,
    // Making it difficult for someone to guess

    s_state = 8773729 * s_state + 3396403; 
    return s_state % 32128; 
}

int main()
{
    std::cout << "Enter the seed value: ";
    int sValue;
    std::cin >> sValue;

    seedMyPRNG(sValue);

    for (int count{ 1 }; count <= 10; ++count)
    {
        std::cout << myPRNG() << '\t';
    }
}

// 1st generation
Enter the seed value: 12
24255   24466   15365   31768   31435   16542   30865   6052    12503   23338

// 2nd generation
Enter the seed value: 9
15900   9423    17058   26005   23336   30299   4014    30625   15284   1383

Much better.

The premise behind seeding is that we want the program to produce different randomized numbers each time it is run. In order to do this, we need some way to vary the seed each time the program is run.

Different seed generation algorithms are available to achieve this purpose.

C++ Support for Randomiziation

C++11 introduced <random>. A dedicated library for RNG. It includes 6 PRNG families for you feast your teeth into.

Type name	Family	Period	Performance
minstd_rand / minstd_rand0	Linear congruential generator	2^{31}	Bad
mt19937 / mt19937_64	Mersenne twister	2^{19937}	Medicore
ranlux24 / ranlux48	Subtract and carry	10^{171}	Horrible
knuth_b	Shuffled linear congruential generator	2^{31}	Awful
rand()	Linear congruential generator	2^{31}	Bad

As of C++20, Mersenne twister (apart from having a cool name) is the only PRNG algorithm with adequate performance.

NOTE: std::rand() from <cstdlib> is not part of <random>. It is a C inheritance with poor statistical quality and limited range, and modern C++ code should reach for <random> instead.

We’ll cover the Mersenne twister in #052 – Crash course on implementing a Mersenne Twister

See you then 🫡 🗒️

NOTE: According to modern PRNG standards, Mersenne Twister is outdated. The biggest issue with Mersenne Twister is that its results can be predicted after seeing 624 generated numbers, making it non-suitable for any application that requires non-predictability. However, for non-critical applications it is sufficient.

In Summary

A PRNG is a deterministic algorithm that simulates randomness by producing a stream of statistically random-looking numbers
It must be seeded to produces a different sequence on every run.
C++’s <random> header gives you a choice of engines, each trading speed against statistical quality. Reach for mt19937 as a sensible default for non-cryptographic work,