Contents

Random Numbers In C++

Want to make some random numbers in C++? Buckle up.

default_random_engine

We start by creating a default_random_engine from C++’s <random> library.

#include <random>

int main() {
  std::default_random_engine myRandomEngine;
}

Now we can use myRandomEngine to generate some random numbers.

#include <iostream>
#include <random>

int main() {
  std::default_random_engine myRandomEngine;
  
  std::cout << myRandomEngine() << " " << std::endl;
  std::cout << myRandomEngine() << " " << std::endl;
  std::cout << myRandomEngine() << " " << std::endl;
}

For me, this produces the output

48271
182605794
1291394886

As you can see, myRandomEngine() returns an unsigned integer. If you’re wondering the range of possible values that may be returned you can do

#include <iostream>
#include <random>

int main() {
  std::default_random_engine myRandomEngine;
  std::cout << "Range: " << myRandomEngine.min() << " to " << myRandomEngine.max() << std::endl;
}

which, for me, yields

Range: 1 to 2147483646

Let’s try running that first code snippet again.

48271
182605794
1291394886

Hmmm, the output is exactly the same as before.. This happens because every time we start our program, myRandomEngine is initialized to the same starting state, 1. You can see this by printing myRandomEngine before calling it.

#include <iostream>
#include <random>

int main() {
  std::default_random_engine myRandomEngine;
  std::cout << "Initial state: " << myRandomEngine << std::endl;  // 1
  // ...
}

If we want to produce a different set of random values when our program runs, we could initialize myRandomEngine with a different seed. For example,

#include <iostream>
#include <random>

int main() {
  std::default_random_engine myRandomEngine(987654321);
  
  std::cout << myRandomEngine() << " " << std::endl;
  std::cout << myRandomEngine() << " " << std::endl;
  std::cout << myRandomEngine() << " " << std::endl;
}

produces

924765591
1764756619
185446553

Of course, the next time we run this program we’ll get those same values. This begs the question, How do we initialize our default_random_engine with a random seed? There are a couple of solutions to this problem..

  1. Use the computer’s internal clock to generate the seed.
#include <iostream>
#include <random>

int main() {
  unsigned seed = std::chrono::steady_clock::now().time_since_epoch().count();
  std::default_random_engine myRandomEngine(seed);
  
  std::cout << myRandomEngine() << " " << std::endl;
  std::cout << myRandomEngine() << " " << std::endl;
  std::cout << myRandomEngine() << " " << std::endl;
}
  1. Use random_device.

random_device

Think of random_device as a tool that measures the current speed of you computer’s fans, multiplies that by the internal temparture of your computer, and then divides that by the amount of your computer’s used storage. Okay, that’s not exactly how random_device works, but the point I’m making is that random_device uses information about your computer’s hardware to generate true random values. Now, you might be asking, Why don’t I just use random_device as my random number generator? A few reasons..

  1. It’s not reproducible. You can’t seed random_device which means you can’t run the exact same program on your computer twice or on others' computers. This can make debugging and performance testing difficult.
  2. It might be slow for generating many random values. Consider the fact that random_device has to reach into your computer’s hardware to generate random numbers.
  3. It can actually be a poor PRNG. If you request enough random numbers in a short timespan, the randomness (i.e. entropy) of those numbers might be low.

While we might not want to use random_device to generate a large sequence of random numbers, it’s a great solution for making a one-time truly random seed for our default_random_engine.

#include <iostream>
#include <random>

int main() {
  // Create a random device and use it to generate a random seed
    std::random_device myRandomDevice;
    unsigned seed = myRandomDevice();
    
    // Initialize a default_random_engine with the seed
    std::default_random_engine myRandomEngine(seed);

    // Print some random values
    std::cout << myRandomEngine() << " " << std::endl;
    std::cout << myRandomEngine() << " " << std::endl;
    std::cout << myRandomEngine() << " " << std::endl;
}

1966422861
273242284
1981214737

If I run this program again, I’ll get three totally different numbers.

Distributions

At this point we know how to generate random integers between myRandomEngine.min() and myRandomEngine.max(). On my machine, this means I can generate random integers between 1 and 2147483646. The obvious next question is How can I generate random integers within my own specified range? For example, suppose I want to generate 5 random integers between -10 and 10 inclusive with equal probability. In this case, I can use C++’s built in uniform_int_distribution.

#include <iostream>
#include <random>

int main() {
    
    // Create a random device and use it to generate a random seed
    std::random_device myRandomDevice;
    unsigned seed = myRandomDevice();
    
    // Initialize a default_random_engine with the seed
    std::default_random_engine myRandomEngine(seed);

    // Initialize a uniform_int_distribution to produce values between -10 and 10
    std::uniform_int_distribution<int> myUnifIntDist(-10, 10);
    
    // Create and print 5 randomly generated values
    for (int i = 0; i < 5; i++) {
        int number = myUnifIntDist(myRandomEngine);
        std::cout << number << std::endl;
    }
}

4
4
-6
9
-8

Notice that we pass myRandomEngine as a parameter to myUnifIntDist(). myRandomDevice, myRandomEngine, and myUnifIntDist each play an important and distinct role.

  • myRandomDevice is responsible for creating a truly random value in order to seed myRandomEngine
  • myRandomEngine is responsible for quickly generating pseudo random integers between 1 and 2147483646
  • myUnifIntDist is responsible for converting those random integers into the range [-10, 10] such that they’re uniformly distributed.

This loose coupling of responsibilities makes it easy to plug in different devices, engines, and distributions. For example, suppose we wanted to generate uniform random real values in the range [0, 1]. We basically just have to change myUnifIntDist from a uniform_int_distribution to a uniform_real_distribution.

#include <iostream>
#include <random>

int main() {
    
    // Create a random device and use it to generate a random seed
    std::random_device myRandomDevice;
    unsigned seed = myRandomDevice();
    
    // Initialize a default_random_engine with the seed
    std::default_random_engine myRandomEngine(seed);
    
    // Initialize a uniform_real_distribution to produce values between 0 and 1
    std::uniform_real_distribution<double> myUnifRealDist(0.0, 1.0);
    
    // Create and print 5 randomly generated values
    for (int i = 0; i < 5; i++) {
        double number = myUnifRealDist(myRandomEngine);
        std::cout << std::fixed << number << std::endl;
    }
}

0.759534
0.066789
0.506626
0.629998
0.927342

Sampling Without Replacement

At this point we know how to sample 3 integers from the range [1, 10] with replacement, but how do we do it without replacement? In other words, how do we sample 3 integers such that none of the results are repeated? The naive solution is to 1) create a vector with all the potential values, 2) shuffle it and 3) pick the first three elements from the result. Let’s see how this works.

#include <iostream>
#include <random>
#include <vector>

int main() {
    
    // Initialize a vector with values [1, 10]
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Create a random device and use it to generate a random seed
    std::random_device myRandomDevice;
    unsigned seed = myRandomDevice();
    
    // Initialize a default_random_engine with the seed
    std::default_random_engine myRandomEngine(seed);
    
    // Shuffle v
    std::shuffle(v.begin(), v.end(), myRandomEngine);
    
    // Get the first three values
    std::vector<int> result(v.begin(), v.begin() + 3);
    for(int i = 0; i < result.size(); i++) std::cout << result[i] << std::endl;
}

6
7
9

The reason this is the naive solution is because, consider what would happen if we wanted to sample 3 integers out of 1 billion without replacement. First we’d have to create a vector with a billion values (memory-inneficient) and then we’d have to shuffle all of them (runtime-inneficient). Fortunately, the late Robert Floyd left us with a clever memory-efficient and runtime-efficient solution. In pseudocode…

In order to sample $ k $ distinct integers from the set $ [1, N] $ (where $ k \leq N $),

  1. Initialize samples = {}, an empty set to store sampled values
  2. For $ r = (N - k) $ to $ (N - 1) $:
    1. Set $ v $ equal to a random integer sampled in the range $ [1, r] $
    2. If $ v $ is not in samples, add it to the set. Otherwise add $ r $ to the set.
  3. Shuffle samples (using the naive technique)

Let’s code this up. (Thanks to Barry for his writeup about this on StackOverflow.)

#include <iostream>
#include <random>
#include <vector>
#include <unordered_set>

std::vector<int> sample_without_replacement(int k, int N, std::default_random_engine& gen){
    // Sample k elements from the range [1, N] without replacement
    // k should be <= N
    
    // Create an unordered set to store the samples
    std::unordered_set<int> samples;
    
    // Sample and insert values into samples
    for (int r = N - k; r < N; ++r) {
        int v = std::uniform_int_distribution<>(1, r)(gen);
        if (!samples.insert(v).second) samples.insert(r);
    }
    
    // Copy samples into vector
    std::vector<int> result(samples.begin(), samples.end());
    
    // Shuffle vector
    std::shuffle(result.begin(), result.end(), gen);
    
    return result;
};

int main() {
    
    // Create a random device and use it to generate a random seed
    std::random_device myRandomDevice;
    unsigned seed = myRandomDevice();
    
    // Initialize a default_random_engine with the seed
    std::default_random_engine myRandomEngine(seed);
    
    // Sample 3 values from 1 Billion
    std::vector<int> result = sample_without_replacement(3, 1000000000, myRandomEngine);
    for(int i = 0; i < result.size(); i++) std::cout << result[i] << std::endl;
}

362678187
389589546
552074333