Serial Random Number Generation

Before C++11¶

Before C++11, there were only two functions for random number generation:

srand() to seed the random number generator
rand() commonly based on an LCG to generate the next random number

#include <iostream> // <-- std::out and std::endl
#include <cstdlib>  // <-- srand() and rand()
#include <ctime>    // <-- time()

srand(time(NULL));
for (auto i = 0; i < 10; ++i)
  std::cout << rand() << std::endl;

And the common practice was to use modulo operator (%), like the way we did in the previous chapter, to bring them into a range:

// generate 10 random numbers from 0 to 99 (a range of 100 values)
for (auto i = 0; i < 10; ++i)
  std::cout << rand() % 100 << ' ';
std::cout << std::endl;

Or an arbitrary range (with an offset):

// generate 10 random numbers from 5 to 14
size_t min = 5, max = 14;
for (auto i = 0; i < 10; ++i)
  // i.e. (rand() % 10) + 5;
  std::cout << (rand() % (max - min + 1)) + min << ' ';
std::cout << std::endl;

Modulo bias ⚠️

Using the modulo operator to bring random numbers into a specific range is generally not a good idea due to the potential for modulo bias.

Modulo bias explained:

Uneven Distribution – When the maximum value of the random number generator (e.g., RAND_MAX in C/C++) is not an exact multiple of the desired range size, applying the modulus operator will result in an uneven distribution of numbers within that range. Some numbers will appear more frequently than others. Example: If RAND_MAX is 32767 and you want numbers in the range 0-99, 32767 % 100 = 67. This means numbers from 0 to 67 will have an extra chance to be generated compared to numbers from 68 to 99, as they can be generated from multiple inputs to the modulus operator (e.g., 0, 100, 200... all result in 0 when modulo 100).
Low-Order Bit Issues – Some ARNGs, particularly older or simpler ones like LCGs, exhibit less randomness in their lower-order bits. Using the modulus operator effectively isolates and utilizes these potentially less random lower bits, further compromising the quality of the “random” numbers.

Consequences of modulo bias:

Non-Uniformity – The resulting numbers will not be uniformly distributed across the desired range, meaning some values are more likely to occur than others.
Reduced Quality of Randomness – For applications requiring high-quality randomness (e.g., simulations, cryptography), modulo bias can introduce exploitable patterns or inaccuracies.

You can get rid of the modulo bias by using an engine with a distribution, introduced in C++11. We’ll cover that in the next section.

Since C++11¶

C++11 brings with it a more complex random-number library that provides multiple engines and many well-known distributions adopted from Boost.Random library. Engines act as a source of randomness to create random unsigned values, which are uniformly distributed between a predefined minimum and maximum; and distributions, transform those values into random numbers:

🎲 Engine

Source of randomness that create random unsigned values, which are uniformly distributed between a predefined minimum and maximum

📊 Distribution

Transform values generated by the engine into random numbers according to a defined statistical probability density function.

Simple demo¶

Let’s see how we can come up with a simple program to use an engine and a distribution to generate random numbers. As there are many ways to bake a cake, we’ll do it in four different ways:

1️⃣ for loop

Notice the exitance of 100 in the output. The distributions in C++11 random library accept closed ranges or intervals. It means unlike the modulo method, 10 and 100 are both included.

2️⃣ std::generate() + lambda

Notice the use of & in the lambda closure to pass the references. That’s especially important for passing engines with huge footprint like Mersenne Twister, but as not much for the distributions.

3️⃣ std::generate() + std::bind()

This is a cleaner and more suitable way of passing both the (reference to) engine and the distribution to the generate() function. Both std::bind() and std::ref() are defined in the functional header.

4️⃣ std::generate_n() + std::bind()

We can also use the std::generate_n() algorithm equally well as sometimes it’s more convenient to pass the number.

Let’s first include the necessary headers and define our output function template:

#include <iostream>   // <-- std::cout and std::endl
#include <iomanip>    // <-- std::setw()
#include <vector>     // <-- std::vector
#include <random>     // <-- std::t19937 and std::uniform_int_distribution
#include <algorithm>  // <-- std::generate() and std::generate_n()
#include <functional> // <-- std::bind() and std::ref()

template <typename RandomIterator>
void print_numbers(RandomIterator first, RandomIterator last)
{   auto n = std::distance(first, last);
    for (size_t i = 0; i < n; ++i)
    {   if (0 == i % 10)
        std::cout << '\n';
        std::cout << std::setw(3) << *(first + i);
    }
    std::cout << '\n' << std::endl;
}

And here are the actual codes to compare:

for loop

generate()+lambda

generate()+bind()

generate_n()+bind()

const unsigned long seed{2718281828};
const auto n{100};
std::vector<int> v(n);
std::mt19937 r(seed);
std::uniform_int_distribution<int> u(10, 100);

for (auto& a : v) // <-- range-based for loop (C++11)
    a = u(r);

// for (size_t i = 0; i < std::size(v); ++i) // <-- old way
//    v[i] = u(r);

print_numbers(std::begin(v), std::end(v));


 35 92 81 73 80 22 78 71 25 66
 66 12 96 35 30 26 68 76 68 63
 63 29 13 65 36 37 98100 63 47
 85 12 50 90 84 47 43 15 78 92
 17 42 98 22 67 43 65 92 55 92
 70 94 28 26 31 69 91 37 57 25
 91 14 18 20 14 25 20 91 51 56
 75 53 83 73 29 86 51 94 13 11
 42 88 88 55 94 11 13 81 12 18
 35 74 31 74 25 77 36 96 23 32

const unsigned long seed{2718281828};
const auto n{100};
std::vector<int> v(n);
std::mt19937 r(seed);
std::uniform_int_distribution<int> u(10, 100);

std::generate
(   std::begin(v)
,   std::end(v)
,   [&]() { return u(r); }
);

print_numbers(std::begin(v), std::end(v));


 35 92 81 73 80 22 78 71 25 66
 66 12 96 35 30 26 68 76 68 63
 63 29 13 65 36 37 98100 63 47
 85 12 50 90 84 47 43 15 78 92
 17 42 98 22 67 43 65 92 55 92
 70 94 28 26 31 69 91 37 57 25
 91 14 18 20 14 25 20 91 51 56
 75 53 83 73 29 86 51 94 13 11
 42 88 88 55 94 11 13 81 12 18
 35 74 31 74 25 77 36 96 23 32

const unsigned long seed{2718281828};
const auto n{100};
std::vector<int> v(n);
std::mt19937 r(seed);
std::uniform_int_distribution<int> u(10, 100);

std::generate
(   std::begin(v)
,   std::end(v)
,   std::bind(u, std::ref(r))
);

print_numbers(std::begin(v), std::end(v));


 35 92 81 73 80 22 78 71 25 66
 66 12 96 35 30 26 68 76 68 63
 63 29 13 65 36 37 98100 63 47
 85 12 50 90 84 47 43 15 78 92
 17 42 98 22 67 43 65 92 55 92
 70 94 28 26 31 69 91 37 57 25
 91 14 18 20 14 25 20 91 51 56
 75 53 83 73 29 86 51 94 13 11
 42 88 88 55 94 11 13 81 12 18
 35 74 31 74 25 77 36 96 23 32

const unsigned long seed{2718281828};
const auto n{100};
std::vector<int> v(n);
std::mt19937 r(seed);
std::uniform_int_distribution<int> u(10, 100);

std::generate_n
(   std::begin(v)
,   n
,   std::bind(u, std::ref(r))
);

print_numbers(std::begin(v), std::end(v));


 35 92 81 73 80 22 78 71 25 66
 66 12 96 35 30 26 68 76 68 63
 63 29 13 65 36 37 98100 63 47
 85 12 50 90 84 47 43 15 78 92
 17 42 98 22 67 43 65 92 55 92
 70 94 28 26 31 69 91 37 57 25
 91 14 18 20 14 25 20 91 51 56
 75 53 83 73 29 86 51 94 13 11
 42 88 88 55 94 11 13 81 12 18
 35 74 31 74 25 77 36 96 23 32

Concluding remarks¶

We came up with four different ways to generate random numbers using an engine and a distribution. The ones more important for us are the last two: std::generate() and std::generate_n() with std::bind(). Why? Because our parallel random number generator library relies on that construct. But that’s the story for the next chapter.

Tutorials

A Primer On Randomness

Tutorials

Parallel Random Number Generation