Generating Random Numbers Using Mersenne Twister

In the previous lesson, we explored the concept of random number generation and how pseudo-random number generators (PRNGs) work. Now let's see how to generate random numbers in C++ programs using one of the most widely-used PRNGs: the Mersenne Twister algorithm.

The Mersenne Twister Algorithm

The Mersenne Twister is a high-quality PRNG that's popular across many programming languages. While newer algorithms exist, Mersenne Twister offers an excellent balance of speed and randomness quality for most applications. C++ provides two variants in the <random> header:

  • std::mt19937 - generates 32-bit unsigned integers
  • std::mt19937_64 - generates 64-bit unsigned integers

Basic Usage of Mersenne Twister

Here's a simple program that generates random numbers using Mersenne Twister:

#include <iostream>
#include <random>

int main()
{
    std::mt19937 generator{}; // create a 32-bit Mersenne Twister

    // Generate and display 20 random numbers
    for (int counter{ 1 }; counter <= 20; ++counter)
    {
        std::cout << generator() << '\t';

        // Print newline every 4 numbers for readability
        if (counter % 4 == 0)
            std::cout << '\n';
    }

    return 0;
}

This program creates a Mersenne Twister object named generator, then calls generator() 20 times to produce random 32-bit unsigned integers. The output might look like:

2357136044    2546248239    3071714933    3626093760
2588848963    3684848379    2340255427    3638918503
1819583497    2678185683    2774094101    1650906866
2994146879    4025852846    2654146808    3897945805
1297663575    2425484413    3907481862    2984484815

Note that generator() uses the function call operator - this is a concise way to invoke generator.operator(), which returns the next value in the random sequence.

Limiting Random Numbers to a Range

While generating numbers between 0 and 4,294,967,295 is interesting, most programs need numbers in a specific range. For example, simulating a card draw might need values 1-52, or a temperature sensor might need values 0-100.

The C++ random library provides random number distributions to solve this problem. A distribution takes the output from a PRNG and transforms it into a different range with specific properties.

The most useful distribution is the uniform distribution, which generates numbers between a minimum and maximum value where every value has equal probability of being selected.

Here's an example simulating temperature readings:

#include <iostream>
#include <random>

int main()
{
    std::mt19937 generator{};

    // Create a distribution for temperatures between -10 and 40 degrees
    std::uniform_int_distribution temperature{ -10, 40 };

    // Simulate 30 temperature readings
    for (int reading{ 1 }; reading <= 30; ++reading)
    {
        std::cout << temperature(generator) << '\t';

        if (reading % 6 == 0)
            std::cout << '\n';
    }

    return 0;
}

Sample output:

15    -3    28    21    7    34
12    -8    19    26    3    38
-5    30    16    -2    25    11
33    8     22    -7    27    14
4     31    18    1     24    37

The key difference is calling temperature(generator) instead of generator() directly. The distribution object transforms the raw random numbers into our desired range.

The Identical Sequence Problem

Run the previous program multiple times. Notice something strange? Every run produces identical results!

While each number appears random relative to the previous one, the entire sequence is deterministic. This happens because we initialize our Mersenne Twister with the same seed value every time (implicitly zero through value initialization).

For many applications, this predictability is unacceptable. Imagine a password generator that creates the same password every time, or a game where enemies always appear in the same locations. We need different sequences each time the program runs.

Seeding with Time

One solution is seeding the PRNG with the current time. Since programs rarely run at the exact same instant, time makes an effective seed:

#include <iostream>
#include <random>
#include <chrono>

int main()
{
    // Seed using time since epoch
    std::mt19937 generator{ static_cast<std::mt19937::result_type>(
        std::chrono::steady_clock::now().time_since_epoch().count()
    ) };

    std::uniform_int_distribution temperature{ -10, 40 };

    for (int reading{ 1 }; reading <= 30; ++reading)
    {
        std::cout << temperature(generator) << '\t';

        if (reading % 6 == 0)
            std::cout << '\n';
    }

    return 0;
}

Now each run produces different output because the seed changes based on when you run the program.

The std::chrono::steady_clock measures time in very small increments (ticks), providing a seed that changes rapidly. While std::chrono::high_resolution_clock offers finer granularity, steady_clock is preferred because it cannot be adjusted by users changing their system clock.

Seeding with std::random_device

A better approach uses std::random_device, which requests random values from the operating system:

#include <iostream>
#include <random>

int main()
{
    std::mt19937 generator{ std::random_device{}() };

    std::uniform_int_distribution temperature{ -10, 40 };

    for (int reading{ 1 }; reading <= 30; ++reading)
    {
        std::cout << temperature(generator) << '\t';

        if (reading % 6 == 0)
            std::cout << '\n';
    }

    return 0;
}

The expression std::random_device{}() creates a temporary std::random_device object and immediately calls its operator() to get a random seed value.

Best practice

Use std::random_device to seed your PRNGs (unless you know it's not properly implemented on your target platform).

Q: Why not use std::random_device for all random numbers?

std::random_device may be slow or deplete a limited pool of random values. It's best used for seeding other PRNGs rather than as the primary random number source.

Seed Only Once

PRNGs should be seeded exactly once during their lifetime. Reseeding can reduce randomness quality or eliminate it entirely.

Here's a common mistake:

#include <iostream>
#include <random>

int getTemperature()
{
    std::mt19937 generator{ std::random_device{}() }; // BAD: created and seeded every call
    std::uniform_int_distribution temperature{ -10, 40 };
    return temperature(generator);
}

int main()
{
    std::cout << getTemperature() << '\n';

    return 0;
}

This code creates and seeds a new generator every time getTemperature() is called, which is inefficient and can produce poor quality randomness.

Best practice

Seed a PRNG once when created, never reseed it.

Addressing Underseeding

Mersenne Twister has an internal state of 19,937 bits (624 32-bit integers for std::mt19937). Seeding with a single integer significantly underseeds the generator, potentially reducing randomness quality.

We can improve seeding using std::seed_seq, which generates additional seed values from initial random data:

#include <iostream>
#include <random>

int main()
{
    std::random_device rd{};
    std::seed_seq seedSequence{
        rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd()
    };
    std::mt19937 generator{ seedSequence };

    std::uniform_int_distribution temperature{ -10, 40 };

    for (int reading{ 1 }; reading <= 30; ++reading)
    {
        std::cout << temperature(generator) << '\t';

        if (reading % 6 == 0)
            std::cout << '\n';
    }

    return 0;
}

By providing 8 random values instead of 1, we give std::seed_seq better material to generate the remaining 616 integers needed to fully seed the generator.

Debugging with Fixed Seeds

When debugging programs using random numbers, it's helpful to ensure consistent behavior across runs. Using a fixed seed value (like 42) makes the program produce identical results every run:

std::mt19937 generator{ 42 }; // Fixed seed for debugging

Once debugging is complete, switch back to proper seeding:

std::mt19937 generator{ std::random_device{}() }; // Normal seeding for production

Troubleshooting

Q: My random number generator produces the same sequence every time.

You probably forgot to seed it properly. Ensure you're seeding with a value that changes each run, like std::random_device{}() or the current time.

Q: My random number generator produces the same number repeatedly.

You're likely reseeding before each random number generation, or creating a new generator each time. Create and seed the generator once, then use it multiple times.

Summary

Mersenne Twister is C++'s standard high-quality PRNG, available as std::mt19937 (32-bit) and std::mt19937_64 (64-bit), providing good balance of speed and randomness for most applications.

Basic usage involves creating a Mersenne Twister object and calling its function call operator () to generate random 32-bit unsigned integers.

Random number distributions transform PRNG output into specific ranges with desired properties. std::uniform_int_distribution generates integers where each value in the range has equal probability.

The identical sequence problem occurs when PRNGs are seeded with the same value every run (typically zero through default initialization), producing predictable sequences that repeat across program executions.

Seeding with time using std::chrono::steady_clock provides different seeds for different program runs, making sequences vary. Steady clock is preferred over high resolution clock because it cannot be adjusted by users.

std::random_device requests random values from the operating system, providing better seed quality than time-based seeding. It's the recommended seeding approach for most applications.

Seed once only—PRNGs should be seeded exactly once when created. Reseeding repeatedly degrades randomness quality or eliminates it entirely, and creating new generators per call is inefficient.

Addressing underseeding with std::seed_seq improves seed quality by generating additional seed values from multiple std::random_device calls, better initializing Mersenne Twister's large internal state.

Fixed seeds for debugging allow reproducible program behavior during testing by using constant seed values, then switching to proper seeding for production use.

Understanding Mersenne Twister's setup and proper usage patterns ensures your programs generate quality random numbers efficiently and correctly.