Random Number Generator in C++

This post is written to keep some simple and useful skills to generate random numbers in c++ and is inspired when I was trying to solve this problem on Hackerrank. What I was trying to do is hash a set of integers by assigning each distinct integer an unique random number and got these random numbers crossed together by applying xor operation one by one. Unfortunately, I got wrong answer at the first several tries and seek help from others’ solutions. Then I used a random number generator named mt19937_64 and pass all test cases. This is fucking amazing, that’s what I thought at that moment :P

We have already got used to use function rand() offered by C programming language, but as C++ standard library becomes more and more completed, it’s essential to know and master some basic usage of cpp random library.

First, there are many kinds of random number generation algorithms, the most frequently used are: Linear Congruential Generators (LCG), Mersenne Twister (MT) and Lagged Fibonacci generator(LFG). To be honest, I’ve never heared of LFG. The pseudo-random number generator used in C is LCG, I think. MT is one kind of the most robust and as well as fast generator, which is developed by two Japanese and is widely used until now.

There are two kinds of different MT implements: std::mt19937 and std::mt19937_64, with the letter generates random number fit in 64-bit integers. The reason that number 19937 in both of names is the length of circle of pesudo-random numbers generated by MT is $2^{19937}$.

In order to generate random sequence, a seed is needed as a start point. Here is an example of using random_device to generate random seed.

But using random_device directly is relatively slow, the wise choice is using it just as a start.
For example, the following code generates random numbers in range 0 to 99 (both inclusive):

std::uniform_int_distribution is implemented as a template for uniform distribution.


References

https://gaomf.cn/2017/03/22/C++_Random/