C++: Pseudo-random Number Generation with STL Library

Introduction

The old way to get random numbers is with srand(time (NULL)) function for initialization, rand() to get the random number, and rand() % maxValue to get a random number between 0 and maxValue. But after I watched Stephan T. Lavavej’s statements on this video, the usage of simple rand() plus modulus paradigm was considered harmful and terrible. Why?

According to C++ documentation of rand(), you’ll see this..

Returns a pseudo-random integral value between ​0​ and RAND_MAX (0 and RAND_MAX included)

Now, see the documentation of RAND_MAX and you will see this..

This value is implementation dependent. It’s guaranteed that this value is at least 32767.

I think the 32767 number was too small for a random number distribution! Also old rand() implementation in most C/C++ compiler using Linear Congruential Generator (LCG) algorithm. Something like this in C code:

LCG Generation in C Code

In the code above, linear congruential generators (LCG) suffer from extreme predictability in the lower bits. The n-th bit (starting from n= 0, the lowest bit) has a period of at most 2n + 1 (i.e., how long until the sequence takes to repeat). So the lowest bit has a period of just 2, the second lowest a period of 4, etc. The function above discards the lowest 16 bits, and the resulting output is at most 32767.

This is not the best generators around and not recommended for serious random-number generation needs, e.g. random usages on the game logic.

So.. What’s the Solution?

Don’t worry, as of C++11 there are much better random number generators available in C++. The C++ <random> header has some features:

• Random generator engines:

1. Mersenne-twister (std::mersenne_twister_engine)
2. LCG (std::linear_congruential_engine)
3. Subtract with carry (std::subtract_with_carry_engine)
4. Non-deterministic seed generator (std::random_device)

• Random number engine adaptors:

1. Discard block (std::discard_block_engine)
2. Independent bits (std::independent_bits_engine)
3. Shuffle order (std::shuffle_order_engine)

• Collections of the random distribution algorithm: Uniform, Bernoulli, Poisson, Normal, Sampling.
• Predefined RNGs: minstd, mt19937, ranlux, knuth, default_random_engine.

Example Usage

Here is a simple example for C++11 random number generator. We will use 64-bit Mersenne Twister engine, which is usually used in most game logic. And an uniform random number distribution.

Example usage of C++ Random Number Generator Library

Mersenne Twister based on the prime 2 to the power of 19937–1. It’s a much higher-quality RNG than rand(), and slightly faster too (389ms to generate 100 million numbers versus 1170ms with rand()). It also produces full 64-bit unsigned outputs between 0 and 2 to the power of 64 - 1, rather than maxing out at a small number 32767.

C++11 also gives you some decent random number distributions. std::uniform_int_distribution gives you perfectly uniform numbers, without the bias of modulo — i.e. rand() % 10000 is more likely to give you a number between 0 and 999 than a number between 9000 and 9999, since 32767 is not a perfect multiple of 10000.

And last, the code seeds the random number generator using a high-precision clock. This is important for avoiding hacks specifically tailored to your code, since using a fixed seed means that anyone can determine what your RNG will output. So… randomizing using a high-resolution seed number can make your code unhackable!

Conclusion

Using the C++11 random library has some advantage over old rand() function, among them:

1. C++ random engines like std::mersenne_twister_engine has much longer period than that of rand(), e.g. it will take its random sequence much longer to repeat itself.
2. It much better statistical behavior.
3. Several different random number generator engines can be initiated simultaneously with different seed, compared with the single “global” seed srand() function.

Have fun coding, and see you in the next article :)