How to generate random numbers

Pseudo Random Number Generators

In the standard library there are three pseudo-random number generators (PRNG) and one almost (sic!) Random number generator - random_device .

linear_congruential_engine , linear congruential generator - the easiest, fastest and lowest quality. Uses the formula x[i] = x[i - 1] * A + B Equivalent to the rand() function. The internal state is one random number, completely predictable.

subtract_with_carry_engine , the late Fibonacci generator is slightly better than the linear congruent generator, has a state of several random numbers.

mersenne_twister_engine , Mersen’s whirlwind is the most qualitative output of random numbers with a practically infinite period, a large state - 624 numbers (2.5 Kb).

The recommended std::mt19937 is std::mt19937 , one of the variants of the Mersen Vortex.

All PRNG are deterministic, so in order for the issue not to be repeated, their state must be initialized with some kind of unique sequence of numbers. To do this, you can use the current time, the more precisely - the better, for example:

 auto now = std::chrono::high_resolution_clock::now(); std::mt19937 random_generator(now.time_since_epoch().count()); 

In some cases, it may be that the current time is not enough, and an additional source of entropy is needed. To do this, you can use the seed_seq utility, which aligns data from several sources of entropy:

 auto now1 = (uint64_t)std::chrono::high_resolution_clock::now().time_since_epoch().count(); uint64_t thread_id = std::hash<std::thread::id>{}(std::this_thread::get_id()); std::random_device random_device; uint64_t entropy = random_device(); auto now2 = (uint64_t)std::chrono::high_resolution_clock::now().time_since_epoch().count(); std::seed_seq seeds{now1, now2, thread_id, entropy}; std::mt19937 random_generator(seeds); 

( seed_seq accepts initializer_list<T> , so the arguments must be of the same type).

Knowing that Mersen’s Vortex has such a larger state, it may be random_device() to completely fill it with random numbers, for example, by calling random_device() 624 times. But it makes no practical sense. The goal is to get a unique sequence of random numbers, and in practice it is enough to simply use the current time.

It should be understood that none of the standard PRNG is cryptographically stable, even the issuance of the Mersen Vortex can be predicted by receiving only 624 numbers. Therefore, the use of a large initialization sequence does not provide any security advantages.

std::random_device

random_device is a random number generator, the implementation of which depends on the standard library.
Depending on the platform and implementation of the standard library, this may be:

• A cryptographically secure system generator of truly random numbers, incl.
  • rdrand processor rdrand (libc ++)
  • read /dev/random or /dev/urandom (libstdc ++)
  • call RtlGenRandom() on Windows (vc ++)
• ordinary PRNG which always gives the same numbers (MinGW)

Moreover, if the implementation uses /dev/(u)random and this file cannot be opened, an exception will be thrown.

Also reading /dev/random can block the work of the program until the moment when the system has accumulated enough entropy.

Therefore, std::random_device should be used only on those systems and compilers that are known to work there as RNG, and be prepared for the fact that this function is very slow compared to PRNG.

( random_device has an entropy() function, but it is useless, because on many platforms it always returns 0 even if RNG is used and not PRNG.)

Distributions

Classes of distributions use the output of random number generators to convert it into a sequence having the desired distribution.

Some classes of distributions, for example, the normal distribution and its derivatives, have an internal state ; therefore, it is not necessary to create a new distribution object for each random number.

 std::mt19937 generator; std::normal_distribution<double> distribution(0, 1); std::vector<double> data; for (auto i = 0; i != 100; ++i) { data.push_back(distribution(generator)); // OK } for (auto i = 0; i != 100; ++i) { // ПЛОХО, не используется состояние распределения data.push_back(std::normal_distribution<double>(3, 1)(generator)); } 

However, even if you create a new distribution for each number, the shape of the distribution changes slightly.

Examples

Replacing code from ::rand() from <cstdlib>

 ::srand(::time(0)); for (int i = 0; i != n; i++) std::cout << ::rand() << '\0'; 

will either use mt19937

 std::mt19937 rand(::time(0)); // Лучше использовать high_resolution_clock for (int i = 0; i != n; i++) std::cout << rand() << '\0'; 

or using random_device (this is normal for programs of the "Hello World" level)

 std::random_device rand; for (int i = 0; i != n; i++) std::cout << rand() << '\0'; 

A more complex example with a functor-generator of random numbers:

 #include <iostream> #include <random> #include <cstdint> #include <chrono> #include <thread> #include <utility> struct GaussGenerator { GaussGenerator(double mean, double stddev, std::uint32_t seed) : engine_(seed), distribution_(mean, stddev) {} GaussGenerator(double mean, double stddev) : distribution_(mean, stddev) { using namespace std; seed_seq seeds{ (uint64_t)chrono::high_resolution_clock::now().time_since_epoch().count(), (uint64_t)chrono::system_clock::now().time_since_epoch().count(), (uint64_t)hash<thread::id>{}(this_thread::get_id()), }; engine_.seed(seeds); } double operator()() { return distribution_(engine_); } std::mt19937 engine_; std::normal_distribution<double> distribution_; }; int main() { GaussGenerator rand(0, 1); for (int i = 0; i != 5; ++i) std::cout << rand() << '\n'; }