GormAnalysisRandom 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..
- 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;
}
- 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..
- 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.
- 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.
- 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 $),
- Initialize samples = {}, an empty set to store sampled values
- For $ r = (N - k) $ to $ (N - 1) $:
- Set $ v $ equal to a random integer sampled in the range $ [1, r] $
- If $ v $ is not in samples, add it to the set. Otherwise add $ r $ to the set.
- 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