TR1 brings a new header into the standard library. called <random>. It defines several random number generators. Until TR1, the only way to generate random numbers in C++ was by using the rand() function. This function, although quite trivial to use and good enough for most of the applications, is not suitable for some applications. For them, developers had to rely on third-party libraries or generators, such as the Marsenne Twister. TR1 defines several good random generators, including the Marsenne twister.
Unfortunately, documentation for these generators is not very good, and MSDN lacks in examples. In this article, I will try to clarify how to use these generators, at least for simple usage.
What Is a Generator?
A random number generator, contrary to a first impression, does not generate truly random numbers, but pseudo-random. Generating numbers imply executing an algorithm, each new number depending one way or another on the last generator number (or a number or more from previous iterations). That means any such algorithm needs an initial value, called a “seed.” An algorithm initialized with the same seed will generate the same sequence of numbers. This is an important aspect because, in practice people, forget to initialize the generator. Being an algorithm based on formulas, a generator is deterministic, and the number it generates is also deterministic. Only a hardware device can generate truly random numbers.
Before TR1
As I mentioned before, until TR1, the only “standard” way for generating random numbers was by using the rand() function. The following example shows how to generate numbers in the interval [0, 9].
int main() { // seeding the generator srand((unsigned int)time(NULL)); // generate 10 "random" numbers for(int i = 0; i < 10; ++i) { std::cout << rand()%10 << " "; } std::cout << std::endl; return 0; }
The first step was to initialize the generator; a common practice (and probably the best) is to use the value returned by the time() function, which is the number of seconds passed since January 1, 1970. If this seeding is forgotten, all the generated sequences will be identical (each time you run the program, the same numbers will be generated).
You also have to pay attention not to call srand(), as shown above, twice in less than a second because, in that case, time() returns the same value and you run into the same problem.
What’s New in TR1?
TR1 introduces three types of ‘entities’: generators, engines, and distributions. A generator is an object that generates pseudo-random numbers. A generator that generates numbers with a uniform distribution is called an engine. Engines and distributions can be combined to generate numbers in two ways:
- Providing an engine to the operator() of a distribution class, or
- Using the variate_generator class to associate a generator and a distribution
Engines
An engine is basically a data source of uniformly distributed numbers in a specific interval. All engines provide the following functions:
- min(): Gives the minimum value that can be returned by engine’s operator();
- max(): Gives the maximum value that can be returned by engine’s operator();
- operator(): Returns values uniformly distributed between min() and max();
- seed(): Initializes the engine with a start value; this function is missing from random_device.
There are two types of engines: simple and combined.
Simple engines
- linear_congruential: A linear congruential generator, generating numbers by using this forumula:
x(i) = (A * x(i-1) + C) mod M
x(i) = (x(i - R) - x(i - S) - cy(i - 1)) mod M
where
cy(i) = x(i - S) - x(i - R) - cy(i - 1) < 0 ? 1 : 0
x(i) = (x(i - R) - x(i - S) - cy(i - 1)) mod 1
where
cy(i) = if x(i - S) - x(i - R) - cy(i - 1) < 0 ? 2-W : 0
Combined engines
- xor_combine: Generates numbers by using two engines; the numbers produced by these two wrapped engines are shifted and composed using this formula:
x(i) = (eng1(i) << S1) ^ (eng2(i) << S2)
typedefs for these engines
- minstd_rand0: Linear congruential generator
typedef linear_congruential<unsigned long, 16807, 0, 2147483647> minstd_rand0;
typedef linear_congruential<unsigned long, 48271, 0, 2147483647> minstd_rand;
typedef mersenne_twister<unsigned long, 32, 624, 397, 31, 0x9908b0df, 11, 7, 0x9d2c5680, 15, 0xefc60000, 18> mt19937;
typedef subtract_with_carry<unsigned long, 1 << 24, 10, 24> _Ranbase; typedef discard_block<_Ranbase, 223, 24> ranlux3; typedef discard_block<_Ranbase, 389, 24> ranlux4;
typedef subtract_with_carry_01<float, 24, 10, 24> _Ranbase_01; typedef discard_block<_Ranbase_01, 223, 24> ranlux3_01; typedef discard_block<_Ranbase_01, 389, 24> ranlux4_01;
typedef subtract_with_carry_01<double, 48, 5, 12> ranlux64_base_01;
Distributions
In TR1 terms, a distribution is a class that transforms a stream of uniformly distributed random numbers (generated by an engine) into a stream of numbers in a particular distribution. The random numbers produced by an engine are always uniformly distributed. To change the distribution of these numbers, you have to use a distribution class.
All distribution classes have the following methods:
- reset(): Clears all cached values that were previously generated by an engine
- operator(): Returns values (one at a time) within a specific distribution (numbers generated by an engine)
TR1 provides the following distribution classes:
- bernoulli_distribution: Generates a Bernoulli distribution
- binomial_distribution: Generates a binomial distribution
- exponential_distribution: Generates a exponential distribution
- gamma_distribution: Generates a gamma distribution
- geometric_distribution: Generates a geometric distribution
- normal_distribution: Generates a normal distribution
- poisson_distribution: Generates a Poisson distribution
- uniform_int: Generates a normal distribution of integer numbers
- uniform_real: Generates a normal distribution of real numbers.
How to Use Engines and Distributions
The simplest way to generate random numbers is to use a generator. The following example uses a linear congruential generator to generate 10 numbers, uniformly distributed.
// linear congruential generator std::tr1::minstd_rand gen; // initialize the generator gen.seed((unsigned int)time(NULL)); // generate the numbers for(int i = 0; i < 10; ++i) { std::cout << gen() << " "; } std::cout << std::endl;
If the seeding is forgotten, the same sequence is generated each time you run the program:
48271 182605794 1291394886 1914720637 2078669041 407355683 1105902161 854716505 564586691 1596680831
If you wanted to generate numbers in the interval [0, 9], you can apply the modulo 10 function on the generated numbers.
for(int i = 0; i < 10; ++i) { std::cout << gen() % 10 << " "; }
The same result, 10 numbers uniformly distributed between 0 and 9, can be generated by combining the generator with a uniform distribution.
// linear congrunetial generator std::tr1::minstd_rand gen; // uniform integer distribution std::tr1::uniform_int<int> dist(0, 9); // initialize the generator gen.seed((unsigned int)time(NULL)); // generate the numbers for(int i = 0; i < 10; ++i) { std::cout << dist(gen) << " "; } std::cout << std::endl;
Another possibility is to associate a generator with a distribution using the variate_generator class.
// linear congrunetial generator std::tr1::minstd_rand gen; // uniform integer distribution std::tr1::uniform_int<int> dist(0, 9); // initialize the generator gen.seed((unsigned int)time(NULL)); // associate a generator with a distribution std::tr1::variate_generator< std::tr1::minstd_rand, std::tr1::uniform_int<int>> combgen(gen, dist); // generate numbers for(int i = 0; i < 10; ++i) { std::cout << combgen() << " "; } std::cout << std::endl;
If seeding had been done after defining combgen, the sequence would have been the same with each run.
// associate a generator with a distribution std::tr1::variate_generator< std::tr1::minstd_rand, std::tr1::uniform_int<int>> combgen(gen, dist); // initialize the generator gen.seed((unsigned int)time(NULL));
0 6 8 9 1 5 3 2 7 0
The reason for this is that a copy of the (uninitialized) generator is made when instantiating combgen. If the type of the generator was a reference type, initialization could have been done after.
// associate a generator with a distribution std::tr1::variate_generator< std::tr1::minstd_rand&, std::tr1::uniform_int<int>> combgen(gen, dist); // initialize the generator gen.seed((unsigned int)time(NULL));
The same thing happens if you use a pointer type:
// associate a generator with a distribution std::tr1::variate_generator< std::tr1::minstd_rand*, std::tr1::uniform_int<int>> combgen(&gen, dist); // initialize the generator gen.seed((unsigned int)time(NULL));
The next sample shows how to use a combined generator. This generator is initialized not with a value, but with a random number produced by another generator.
// engines std::tr1::minstd_rand gen1; std::tr1::mt19937 gen2; std::tr1::linear_congruential<unsigned long, 33614, 0, 2147483647> seeder; // initialize the seeder seeder.seed((unsigned int)time(NULL)); // combined engine std::tr1::xor_combine< std::tr1::minstd_rand, // first engine // shifting value for the numbers from the first engine 7, std::tr1::mt19937, // second engine // shifting value for the numbers from the second engine 13 > xorgen(gen1, gen2); // exponential distribution std::tr1::exponential_distribution<float> expdist(2); // initialize the combined generator xorgen.seed(seeder); // generate numbers for(int i = 0; i < 10; ++i) { std::cout << xorgen() << " "; } std::cout << std::endl;
Conclusions
With TR1, the standard C++ library becomes richer in the possibilities of generating random number generators. Engines and distributions can be combined to generate numbers to meet various requirements. Perhaps, in the future, MSDN also will be enriched with examples for their usage. In the meantime, hopefully this article provides a good introduction for that.