A TR1 Tutorial: Generating Random Numbers

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

• marsenne_twister: An implementation of the Marsenne twister. This generator keeps a value on W * (N-1) * R bits; each time a number needs to be generated, it extracts W bits. When all bits have been used it, twists the large value by shifting and mixing the bits so that it has a new set of bits to extract from.
• subtract_with_carry: Generates numbers based on the following formula:

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

• subtract_with_carry_01: Generates numbers based on the following formula:

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

• random_device: Generates random numbers by using an external device.

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)

• discard_block: Uses another engine to produce numbers; some of these are discarded. The engine is parameterized with another engine, the length of the used sequence (P) and the length of the discarded sequence (R). The generated returns a new number at the first R calls. Then, it generates another P-R numbers that are discarded, and the process is repeated.

typedefs for these engines

• minstd_rand0: Linear congruential generator

typedef linear_congruential<unsigned long, 16807, 0,
   2147483647>
   minstd_rand0;

• minstd_rand: Linear congruential generator

typedef linear_congruential<unsigned long, 48271, 0,
   2147483647>
   minstd_rand;

• mt19937: Marsenne twister

typedef mersenne_twister<unsigned long, 32, 624, 397, 31,
   0x9908b0df,
   11, 7, 0x9d2c5680, 15, 0xefc60000, 18> mt19937;

• ranlux_base_01: Generator based on subtraction with carry
• ranlux3 si ranlux4: Discarding generator based on subtraction with carry

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;

• ranlux3_01 si ranlux4_01: Discarding generator based on subtraction with carry

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;

• ranlux_64_01: Generator based on subtraction with carry

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.