Generating Random Numbers in C++

From Dice to C++

Rather than roll a die, we want to generate a random integer between 0 and \( N-1 \) (inclusive) in our code, using a pseudorandom-number generator (PRNG).

This is one example whwere C++'s power and flexibility comes at the cost of simplicity—when you just want to do something like get a random number in a certain range, it can feel like a lot of scaffolding is needed to get there. In this lesson, and the upcoming assignment, we felt like you had enough things going on without needing to learn all the ins and outs of C++'s random-number generation facilities, so we created a simple-to-use random-number generator for you to use: the RandUInt32 class.

The CS 70 RandUInt32 Class

The CS 70 server has a library called randuint32. You can include it in your code with:

#include <cs70/randuint32.hpp>

The library defines a class called RandUInt32.

Instances of that class can generate uniformly distributed random integers. You access those numbers by calling the class's get(…) member function, which takes in a number N, and returns a random integer between 0 and N-1 (and thus has N distinct possible values).

Any time you want to compile and link code that uses the RandUInt32 class, you will need to tell the linker

• -lranduint32 to link in the randuint32 library.

So if your program is called myrand.cpp, you would compile to a .o file like normal and then link with our random-number library. For example,

clang++ -c -std=c++17 -Wall -Wextra -pedantic myrand.cpp
clang++ -o myrand myrand.o -lranduint32

Your Turn

The following program generates a RandUInt32 object, then calls its get(…) member function 6000 times to generate numbers between 0 and 5 (i.e., six different outcomes) and summarizes the results:

#include <cs70/randuint32.hpp>
#include <cstddef>
#include <iostream>

constexpr size_t TOTAL_ROLLS = 6000;
constexpr size_t DICE_SIDES = 6;

int main() {
    RandUInt32 rand;

    size_t counts[DICE_SIDES] = {0, 0, 0, 0, 0, 0};
    for (size_t i = 0; i < TOTAL_ROLLS; ++i) {
        size_t roll = rand.get(DICE_SIDES);
        ++counts[roll];
    }

    std::cout << "Results from " << TOTAL_ROLLS << " dice rolls" << std::endl;
    for (size_t i = 0; i < DICE_SIDES; ++i) {
        std::cout << i << "\t" << counts[i] << std::endl;
    }
    return 0;
}

We'll give you two options for running this code. The first way mirrors how you'd use it in your own code for assignments. Use the link below to open the code in GitHub, and then clone that repository in Visual Studio Code and run it on the CS 70 server.

• Open this code on GitHub

Or, alternatively, if that all seems like too much trouble, we've made it so you can run the code in Online GDB. (But for this case, we had to do a few tricks to let that environment use our library, so we made a small tweak to the #includes.)

• Run this code in Online GDB

When “Random” Isn't Actually Random

When our algorithms need to make a random choice, they don't want to wait around while someone rolls real dice out in the world. They want to decide very quickly, otherwise that wait would become a bottleneck for the algorithm's performance.

In fact, modern random-number generators on today's machines are really fast. Good ones can produce a new random number in under a nanosecond!

To run quickly, random-number generators use deterministic algorithms that produce a long sequence of random-looking numbers that eventually cycles back and repeats.

For example, the Mersenne Twister produces a staggering \( 2^{19937} - 1 \) outputs before it repeats itself (known as the period of the PRNG).

Other modern PRNGs are smaller than the Mersenne Twister, but still have staggeringly large periods.

If you start a modern PRNG from some arbitrary place in its period, you'll be producing a stream of random-looking numbers that no one on Earth has ever seen before.

A lot of real-world randomness has some bias to it (e.g., flipping a fair coin is biased towards the side that was up when you started), and some processing is required to remove that bias. In contrast, good PRNGs produce random sequences that pass a broad range of statistical tests.

For many PRNGs, even if you see lots of their output, you still can't easily figure out where in their deterministic sequence they are, so they aren't preditable in that sense.

But PRNGs do provide reproducability. If you start the sequence of outputs at the same place, you get the same results.

Seeding...

Where you start your PRNG is known as the seed.

If you give your PRNG the same seed twice, it will produce the same sequence of numbers both times!

If your program's behavior depends on that sequence of numbers, you'll get the same outcomes in both runs, even though your program's behavior is “random”.

When you default construct our RandUInt32 class, it chooses the seed randomly.

One example of an entropy source is the high-resolution clock in the machine. It would be very hard to know exactly which nanosecond of the clock we started our program, so we can use that (perhaps scrambled up a bit) to make a seed value.

Even better-quality randomess is maintained by the operating system, based on all kinds of entropy sources the computer has access to (like when you last pressed a key, or when network packets arrive).

The key thing is that although a random seed value might be a bit slow to compute (and require us to find a good entropy source to use), once we've initialized the generator, it can then run quickly, generating lots of good (pseudorandom) randomness.

A Quick Demo

This program seeds the random-number generator before generating 10 numbers between 0 and 100.

Edit your myrand program to change main to match the code below, recompile and run it, and let us know what happens!

int main() {
    RandUInt32 rand_{1994}; // Here, our seed is a favorite year....

    for (size_t i=0; i < 10; ++i) {
        if (i > 0) {
            std::cout << ", ";
        }
        std::cout << rand_.get(100);
    }
    std::cout << std::endl;

    return 0;
}

If you think that's crazy, try the seed 1279079580, especially if you consider 3 to be a lucky number.

Final Thoughts on Seeding & Usage

Takeaways

• Because RandUInt32 can seed itself with a good seed, only override it with a specific seed as a bonus feature for debugging.
• Although RandUInt32 can seed itself, that doesn't mean you should create new RandUInt32 objects all the time. As much as possible, just create one that gets used a lot.
  • For example, in the homework, one RandUInt32 object per tree object is a good way to go.
• Use the get() member function to get random numbers within a certain range.

(When logged in, completion status appears here.)