CS 70

Random Numbers

It is often useful to generate a random number. Perhaps you want to simulate a stochastic process, or maybe you need to randomly decide where you should insert an item into a data structure. There are many ways generate random numbers in C++.

Do Not Use Any C-Style PRNGs in CS 70

One option always available to C++ programmers is to do things the way a C programmer would, so you may have seen code that uses one of the various random-number generators available in C. In this case, you should not use any of them.

Specifically…

Never use the C Library PRNG, rand()

The C standard library provides a function rand, but we prohibit its use in CS 70. The C standard describes it as follows:

Description

The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX inclusive.

The rand function is not required to avoid data races with other calls to pseudo-random sequence generation functions.

Recommended Practice

There are no guarantees as to the quality of the random sequence produced and some implementations are known to produce sequences with distressingly non-random low-order bits. Applications with particular requirements should use a generator that is known to be sufficient for their needs.

Environmental limits

The value of the RAND_MAX macro shall be at least 32767

The potentially very limited range of rand() and its potential low quality are big reasons not to use it, not just in CS 70, but almost anywhere.

Running cpplint on code that does use rand will generate an error to remind you not to use it. Unfortunately, it is mostly concerned with just one of the issues (data races causing problems for multi-threaded code) and so recommends a POSIX variant of function, rand_r, but that does not address the other issues with using rand.

Don't Use POSIX Library PRNGs Either

Linux, Unix systems (including macOS), and Windows all support the POSIX C library, which augments the Standard C library with additional functionality, including “improved” random number generation facilities, specifically random and drand48 (and their thread-safe _r variants).

These are generators with a C-style interface, and are not of particularly high quality. Although widely used in various code that makes casual use of random numbers, don't use them in CS 70.

The CS 70 Random Number Library

For CS 70, we have provided a simple library for generating random numbers. Our library is a wrapper for a very robust pseudorandom number generator. It is included in the CS 70 student Docker image.

Our library generates random unsigned integers with 32 bits. Hence, it is named randuint32.

In order to use randuint32, you need to include the header in the file where you want to use it:

#include <cs70/randuint32.hpp>

The CS 70 Random Number Library Interface

We provide the following functionality:

  • RandUInt32(): a default constructor. A default constructed RandUInt32 object will generate a different random sequence of numbers every time it is used.

  • RandUInt32(size_t seedval): a parameterized constructor. A RandUInt32 constructed with a given seedval will generate the same random sequence every time it is used. This is very useful for debugging purposes.

  • get(size_t max): calling a RandUInt32 object’s .get(max) function with the max parameter will return the next pseudo-random unsigned int in the range [0, max - 1].

  • get(): calling a RandUInt32 object’s .get() function with no parameters will return the next pseudo-random unsigned int in the range [0, 2^32 - 1]. You probably want to use the other get(…) function, not this one.

Compiling

In order to compile, you will need to link with the library by adding -lranduint32 to your linking step. For example, this is the Makefile for the following two examples.

CXX = clang++
CXXFLAGS = -g -Wall -Wextra -pedantic
LIBS = -lranduint32
TARGETS = rand-test dice

# Note: The rules below use useful-but-cryptic make "Automatic variables"
#       to avoid duplicating information in multiple places, the most useful
#       of which are:
#
#   $@  The file name of the target of the rule
#   $^  The names of all the prerequisites, with spaces between them.
#   $<  The name of the first prerequisite
#
# For GNU make, you'll find that it supports quite an extensive list, at
#   http://www.gnu.org/software/make/manual/html_node/Automatic-Variables.html

all: $(TARGETS)

rand-test: rand-test.o
    $(CXX) $^ -o $@ $(LIBS)

rand-test.o: rand-test.cpp
    $(CXX) $(CXXFLAGS) -c $<

dice: dice.o
    $(CXX) $^ -o $@ $(LIBS)

dice.o: dice.cpp
    $(CXX) $(CXXFLAGS) -c $<

clean:
    rm -rf $(TARGETS) *.o

Example 1: Generating repeatable or non-repeatable pseudo-random sequences

This example shows how to use RandUInt32 in two different ways to generate random sequences.

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

int main() {
    // We are going to generate some number of random samples
    constexpr size_t NUM_TO_GENERATE = 10;

    // Let's generate numbers between 0 and 99
    constexpr size_t RAND_RANGE = 100;

    // Using a specified seed, we can create a pseudorandom
    // number generator that always produces the same
    // random-seeming sequence on every run of the program
    //
    // This is good for debugging programs that need to use
    // random numbers so that you get the same 'random'
    // sequence while you test your code
    size_t SEED = 17;

    // pass the seed to to construct a CS70random object
    RandUInt32 rng_repeatable{SEED};

    // We can now generate the same sequence each time we run the program
    std::cout << "Reproducible pseudorandom sequence:" << std::endl;
    for (size_t i = 0; i < NUM_TO_GENERATE; ++i) {
        std::cout << rng_repeatable.get(RAND_RANGE) << " ";
    }
    std::cout << std::endl;

    // If we do not pass a seed to the constructor, we will get
    // a different random sequence every time we run the program
    RandUInt32 rng_nonrepeatable;

    // We can now generate a different sequence each time we run the program
    std::cout << "Different pseudorandom sequence for every run:" << std::endl;
    for (size_t i = 0; i < NUM_TO_GENERATE; ++i) {
        std::cout << rng_nonrepeatable.get(RAND_RANGE) << " ";
    }
    std::cout << std::endl;

    return 0;
}

Running the code three times gives these results. Notice the reproducibility of the first method each time the program is run.

cs70 DOCKER > ./rand-test 
Reproducible pseudorandom sequence:
76 59 10 68 46 25 13 56 54 90 
Different pseudorandom sequence for every run:
74 98 74 99 72 40 93 62 89 71

cs70 DOCKER > ./rand-test
Reproducible pseudorandom sequence:
76 59 10 68 46 25 13 56 54 90 
Different pseudorandom sequence for every run:
86 96 54 90 5 81 50 43 1 93

cs70 DOCKER > ./rand-test
Reproducible pseudorandom sequence:
76 59 10 68 46 25 13 56 54 90 
Different pseudorandom sequence for every run:
65 47 99 49 19 21 16 2 73 51

Example 2: Simulating a dice rolling game

In this example, we simulate rolling a die many times, trying to get a winning number. We count the number of times we win and get a point, and then estimate the winning probability.

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

using std::cout;
using std::endl;

int main() {
    // Let's simulate a game where we are trying to roll
    // a die and get the winning number
    constexpr size_t NUM_OF_DICE_ROLLS = 1000;
    constexpr size_t DICE_SIDES = 6;
    constexpr size_t WINNING_NUMBER = 2;

    // create a random number generator with no seed
    RandUInt32 rng_nonrepeatable;

    size_t num_wins = 0;

    for (size_t i = 0; i < NUM_OF_DICE_ROLLS; ++i) {
        unsigned int dice_roll = rng_nonrepeatable.get(DICE_SIDES);
        if (dice_roll == WINNING_NUMBER) {
            // you get 1 point for rolling the winning number
            cout << '+';
            ++num_wins;
        } else {
            // you get 0 points for rolling anything else
            cout << '_';
        }
    }

    // In the code below, notice that we convert the numerator to a double,
    // otherwise, we would get integer division and have a value of 0 for
    // the result!  We either do that with an explicit conversion, or by
    // multiplying by a double constant.

    double expected_wins = double(NUM_OF_DICE_ROLLS) / DICE_SIDES;
    double expected_percent = 100.0 / DICE_SIDES;
    double actual_percentage = 100.0 * num_wins / NUM_OF_DICE_ROLLS;

    cout << "\n\nYou won " << num_wins << " points out of " << NUM_OF_DICE_ROLLS
         << " trials.\n\n"

         << "We'd expect to win " << expected_percent << "% of games ("
         << expected_wins << " wins on average)\n"
         << "In this simulation, we won " << actual_percentage << "% of games"
         << endl;
    if (std::abs(actual_percentage - expected_percent) <= 0.5) {
    cout << "Whoa, that's pretty close!" << endl;
    } else if (actual_percentage < expected_percent) {
    cout << "Better luck next time!" << endl;
    } else if (actual_percentage > expected_percent) {
    cout << "I guess we got lucky!" << endl;
    }

    return 0;
}

Running this program three times gave the following output:

cs70 DOCKER > ./dice
_+_+______++_____+____+__++____+_++_____________+________+_______+___+___++_________+____________________+_+_+____+___+______________+_____+______+________+________++_+_+_______+________+_+____+_+_+________________+_+____+_______+________________________+++_________++______+__+____+_+_____________+___+________+_+____+____________+_+_+________________+____++___+___+________________+_____+___________+_+_______+___________________++___+_++_____+______+_+________+___+______________+____+_____+___+_+_++____________+_______+__+_+___+__+_________________+_____+__+____+__________++___+_____++________+____________+_____+_____+_________+_______________++_________+____+__+____++______+____+_____+_____+___+___+_________+_+_________+__+____+________+_++____++_____+++_____+___+_____________+__+______+____________+_+____+____+____++_+__________+_________+____+___+_+___+____________+_+______++____+___+_________________+______+_+______+___+_____++_________+_____+___+_____+____+__________+___+___+___+_+

You won 172 points out of 1000 trials.

We'd expect to win 16.6667% of games (166.667 wins on average)
In this simulation, we won 17.2% of games
I guess we got lucky!

cs70 DOCKER > ./dice
____+____________+__________+_______+___________________________+______+_+_____+_____________+++___+___++__________++__+_+____________+___+__________________________+__________________+_______+______+_______+___+_____+_________+_+__+_+__________+______________________+__+___+____________+____________+________+__+__+___+_+_____+__+________+__+_____+_+++_____________+___++_________+______+_+__+____+___+__+_++_________+___+___+_____________++____+__________+____+_________+______+_+___+___+__+________+_+_____________+______________+_____+______+____+_______________+___+______+______++_____+_____+__________+_+_____+_____+_+__+___+___+_+_________+____+_________________+___+______________+___++___+_____________+___________++______+____+___+_+_____+_+________+___________++____+_______+____+_++______+__+_____________________++____++___+____+___+_____________+___________+______________________________+__+___+_++____________+__+++___________________+_+_++______________++____+_______+____+_____+__

You won 154 points out of 1000 trials.

We'd expect to win 16.6667% of games (166.667 wins on average)
In this simulation, we won 15.4% of games
Better luck next time!

cs70 DOCKER > ./dice
+_______________++_+_+___+________+_+___++________+_________++______+________+_______________________++_________++______+_________+_____+++__________________+____+_____+______+_++______+__+__________+__+________+___+_____+____+____+__++____________++_+_+___________+___+_________+_+__+__+_+_____+_______+____+___________________+__________+__++__+___+______+_+______________+_+______________++____________++_++_______+__++___++_______+___+_______________________+___+_+__++_+__+______++______________++_+_+______++___+_______+_+_____+____________+________________+_______+___________+__________+_______+___________+______________+_______+_________________________+_________+__+___+_____+___________+_____+___________________++___________+__+_+_+__+_+________+_+_________+______+____+_+_+_______________+______+____+_____________+______________+_________+__+_++_____+________+_____+___+_++_+________+_+_+_______+____+____+++____+_+__+_+____+__+____++_____________+____++________+____________+____+__+_

You won 167 points out of 1000 trials.

We'd expect to win 16.6667% of games (166.667 wins on average)
In this simulation, we won 16.7% of games
Whoa, that's pretty close!

(When logged in, completion status appears here.)