Random number generation in C++11: how to generate, how does it work? [closed]

I recently came across new way to generate random numbers in C++11, but couldn't digest the papers that I read about it (what is that engine, maths term like distribution, "where all integers produced are equally likely").

So can anyone please explain

what are they?
what does they mean?
how to generate?
how do they work?
etc

You can call it all in one FAQ about random number generation.

Solution 1:

The question is way too broad for a complete answer, but let me cherry-pick a couple of interesting points:

Why "equally likely"

Suppose you have a simple random number generator that generate the numbers 0, 1, ..., 10 each with equal probability (think of this as the classic rand()). Now you want a random number in the range 0, 1, 2, each with equal probability. Your knee-jerk reaction would be to take rand() % 3. But wait, the remainders 0 and 1 occur more often than the remainder 2, so this isn't correct!

This is why we need proper distributions, which take a source of uniform random integers and turn them into our desired distribution, like Uniform[0,2] in the example. Best to leave this to a good library!

Engines

Thus at the heart of all randomness is a good pseudo-random number generator that generates a sequence of numbers that uniformly distributed over a certain interval, and which ideally have a very long period. The standard implementation of rand() isn't often the best, and thus it's good to have a choice. Linear-congruential and the Mersenne twister are two good choices (LG is actually often used by rand(), too); again, it's good to let the library handle that.

How it works

Easy: first, set up an engine and seed it. The seed fully determines the entire sequence of "random" numbers, so a) use a different one (e.g. taken from /dev/urandom) each time, and b) store the seed if you wish to recreate a sequence of random choices.

#include <random>

typedef std::mt19937 MyRNG;  // the Mersenne Twister with a popular choice of parameters
uint32_t seed_val;           // populate somehow

MyRNG rng;                   // e.g. keep one global instance (per thread)

void initialize()
{
  rng.seed(seed_val);
}

Now we can create distributions:

std::uniform_int_distribution<uint32_t> uint_dist;         // by default range [0, MAX]
std::uniform_int_distribution<uint32_t> uint_dist10(0,10); // range [0,10]
std::normal_distribution<double> normal_dist(mean, stddeviation);  // N(mean, stddeviation)

...And use the engine to create random numbers!

while (true)
{
  std::cout << uint_dist(rng) << " "
            << uint_dist10(rng) << " "
            << normal_dist(rng) << std::endl;

}

Concurrency

One more important reason to prefer <random> over the traditional rand() is that it is now very clear and obvious how to make random number generation threadsafe: Either provide each thread with its own, thread-local engine, seeded on a thread-local seed, or synchronize access to the engine object.

Misc

An interesting article on TR1 random on codeguru.
Wikipedia has a good summary (thanks, @Justin).
In principle, each engine should typedef a result_type, which is the correct integral type to use for the seed. I think I had a buggy implementation once which forced me to force the seed for std::mt19937 to uint32_t on x64, eventually this should be fixed and you can say MyRNG::result_type seed_val and thus make the engine very easily replaceable.

Solution 2:

A random number generator is a equation that, given a number, will give you a new number. Typically you either provide the first number or its pulled from something like the system time.

Each time you ask for a new number it uses the previous number to execute the equation.

A random number generator is not considered very good if it has a tendency to produce the same number more often than other numbers. i.e. if you wanted a random number between one and 5 and you had this distribution of numbers:

1: 1%
2: 80%
3: 5%
4: 5%
5: 9%

2 is generated FAR more often than any other number, so it is more likely to be produced than other numbers. If all numbers were equally like you would have a 20% chance of getting each number every time. To say it another way, the above distribution is very uneven because 2 is favored. A distribution with all 20%'s would be even.

Typically, if you want a true random number you would pull data from something like weather or some other natural source rather than a random number generator.