Chapter 13. Random Number Generators

The theory of probabilities is at bottom nothing but common sense reduced to calculation.

—Théorie Analytique des Probabilities
PIERRE-SIMONE LAPLACE, TRANSLATED BY ANGELA PAO

Applications often need to generate numbers with varying degrees of unpredictability. For a card game, if players can predict the next card, the odds change. For a Monte Carlo integration,^[1] if the selected input values show too strong a pattern, the value of the integral might not be accurate. For generating security keys, if a hacker can predict the generated keys—perhaps with detailed knowledge of the key-generation algorithm— security is compromised. Standard C and C++ offer the pair of functions rand and srand for generating streams of random numbers. The TR1 library offers several types for generating streams of uniformly distributed random numbers, as well as several other types for converting streams of uniformly distributed numbers into streams with other distributions.

An engine is a class or template whose objects act as a source of random numbers uniformly distributed between a minimum and maximum value. A distribution is a class or template whose objects transform a stream of uniformly distributed random numbers obtained from an engine into a stream of random numbers with a particular distribution. An engine object can be passed directly to the function call operator of a distribution object to generate the next value in this stream, or an instance of the template variate_generator can be created to encapsulate an engine object and a distribution object in a single object. The random number generators in the TR1 library are described in the header <random>.

The preceding synopsis and the sections that follow use template parameter names to designate particular sets of types, as follows.

• IType: a signed integral type or an unsigned integral type, which must be one of short, int, long, unsigned short, unsigned int, or unsigned long

• UType: an unsigned integral type, which must be one of unsigned short, unsigned int, or unsigned long

• RType: a floating-point type, which must be one of float, double, or long double.

The TR1 library specification gives requirements for three categories of random number generators, referred to as uniform random number generators, random number engines,^[2] and random distributions. We’ll look at the requirements for random number engines in Section 13.1 and for random distributions in Section 13.5.

A uniform random number generator has a function call operator that returns the next value in the random sequence, two member functions min and max that give the minimum and maximum values that can be generated, and a nested type name result_type that names the type returned by those three members. More formally, for every generator type Gen and object gen of type Gen, the following expressions must be valid.^[3]

Getting Values

• Gen::result_type: the typedef is a synonym for the type of the expressions gen(), gen.min(), and gen.max().

• gen.min(): the value of the expression is the minimum value returned by gen().

• gen.max(): the value of the expression is the maximum value returned by gen(). When result_type is an integral type, this is the maximum value that can be returned;^[4] when result_type is a floating-point type, this is the smallest value greater than all values that can be returned.^[5]

• gen(): repeated invocations of the expression produce a sequence of random values between min() and max().

As we’ll see, random number engines satisfy these requirements, so they can be used wherever a generator is required.

13.1. Random Number Engines

A random number engine is a class or template whose objects act as a source of random numbers uniformly distributed between a minimum and maximum value. Engines are of two kinds. A simple engine produces random numbers directly. A compound engine obtains random numbers from one or more other engines and generates a stream of uniformly distributed random numbers from those values.^[6]

Different classes use different techniques to generate random numbers, but all engines that conform to the TR1 library specification provide several fundamental operations. You can set the state of the engine with constructors and the seed member functions, you can get the next value in the random sequence with the function call operator, and you can examine the range of values that can be generated, by calling the member functions min() and max().

Example 13.1. Basic Properties (random/engprops.cpp)

In addition, you can write the state of an engine to an output stream with a stream inserter, and you can read the state from an input stream with a stream extractor. You can also compare two engines of the same type for equality.

Example 13.2. Reading and Writing (random/engrw.cpp)

More formally, for every engine type Eng and objects eng and eng1 of type Eng, the following expressions must be valid.

Setting the State

• Eng(): the constructor constructs an object whose initial state is determined as if by calling seed().

• Eng(x0), where x0 is a value of an integral type: the constructor constructs an object whose initial state is determined as if by calling seed(x0).

• Eng(s), where s is a callable object (see Section 6.1) that takes no arguments and returns an unsigned integral value: the template constructor constructs an object whose initial state is determined as if by calling seed(s).

• eng.seed(): the member function sets the internal state of the engine to a default value.

• eng.seed(x0), where x0 is a value of an integral type: the member function sets the state of the generator to a value determined by x0.

• eng.seed(s), where s is a callable object that takes no arguments and returns an unsigned integral type: the function sets the generator’s internal state to values generated by successive calls to s().

Getting Values

• The requirements are the same as for a generator, given earlier. For an engine object eng, the expression eng() returns values that are uniformly distributed between eng.min() and eng.max().

Reading, Writing, and Comparing

• eng == eng1: true if eng and eng1 have the same state, so that the two objects will generate the same stream of values.

• eng != eng1: true if eng == eng1 is false.

• os << eng: sets the format flags of the output stream os to ios_-base::dec|ios_base::fixed|ios_base::left and sets the fill character to space, then writes the state of eng to the output stream—with one or more spaces separating adjacent numbers—then restores the format flags and fill character to their settings before the operation began.

• is >> eng1: reads the new state of eng1 from the input stream is. The contents of the input stream must have been written by a call to os << eng, where eng is an engine of the same type as eng1, and os used the same locale, character type, and character traits type as is.^[7]

13.2. Engine Templates in the TR1 Library

The TR1 library provides six templates that define engines. Sections 13.2.1– 13.2.4 describe the basic engines; Sections 13.2.5 and 13.2.6, compound engines. The six templates satisfy all the requirements for engines, so you can use them as patterns if you write your own engine. You don’t have to follow any of these patterns, though, so long as your engine provides all the required operations.

The library also provides a class named random_device (Section 13.3) and nine predefined engines, in the form of typedefs for particular template specializations (Section 13.4).

In the discussion that follows, some of the details are in the template declaration itself. In the text following the declaration, I’ll explain the things that need more details than can easily fit in the declaration, including the details of the algorithm that the template implements and the contents of the engine’s state.

Every engine has a state that is used to generate successive values. The size of an engine’s state and its text representation, written by the stream inserter and read by the stream extractor, are exactly specified by TR1.^[8] As a result, applications compiled with different implementations of the library and running on different hardware can share an engine’s state. This is used for parallelizing calculations and for checkpointing. Parallelizing a calculation means distributing parts of the calculation to different processors, which requires being able to start an engine at a known state, even with a different implementation of that engine. Checkpointing means saving a long-running application’s state periodically so that the calculation can be resumed on the same machine if it gets interrupted. This does not require portability across systems.

13.2.1. Basic Engine linear_congruential

The class template describes a simple engine that produces values of type UType, using the recurrence relation x_i=(A*x_i-1+C) mod M.

If the value of the template argument M is 0, it is treated as if it were std::numeric_limits<UType>::max() + 1.^[9] The type argument UType must be an unsigned integral type that is large enough to store values up to M - 1. The values of the template arguments A and C must be in the range [0, M-1].

The size of the engine’s state is 1, and its value is the last value returned by operator() or, if no call has been made to operator(), the seed value.

The member function seed(unsigned long x0) sets the state of the engine to the value x0, unless x0 is 0 and C mod M is 0, in which case it sets the state to 1.^[10]

This template implements the commonly used linear congruential algorithm. If you choose the template arguments carefully, it can produce long random sequences. If you choose badly, the sequences can be short, or they can show other patterns. The predefined generators minstd_rand0 (see Section 13.4.1) and minstd_rand (see Section 13.4.2) are well understood and have good properties.

Linear congruential engines as a rule are fast, especially if the value of M is the same as the size of an unsigned integral type, which avoids having to do the final division on most hardware. The implementation should use an efficient integral type to hold intermediate values when it computes a new value. However, if M is larger than the square root of the system’s largest unsigned integral value, the engine can be quite slow, because the implementation may have to resort to multiple-precision arithmetic.

13.2.2. Basic Engine mersenne_twister

The class template describes a simple engine that produces values of type UType by applying the following recurrence relation:

• y_i = (UM &x_i-N)|(LM &x_i-(N-1))

• If the lowest bit of y_i is set, x_i = x_i-(N-M) Λ(y_i >>1)ΛA

• Otherwise, x_i = x_i-(N-M) Λ(y_i >>1)

then computing the result, o(x_i), from the new value of x_i, as follows:

• z1i = x_i Λ(x_i >>U)

• z2i = z1i Λ((z1i <<S)&B)

• z3i = z2i Λ(z2i <<T)&C)

• o(x_i)= z3i Λ(z3i >>1)

where all the computations are performed modulo 2^W, UM is a value of type UType with only its upper W-R bits set, and LM is a value of type UType with only its lower R bits set.

The type argument UType must be an unsigned integral type whose width is at least W bits; that is, it must be able to hold values up to 2^W - 1. In addition:

• 1 ≤ M ≤ N

• 0 ≤ R, U, S, T, L ≤ W

• 0 ≤ A, B, C ≤ 2 ^W - 1

The size of the engine’s state is N, and its value is the sequence of values x_i—N, …,x_i—1, in that order.

The member function seed(unsigned long x0) sets x_-N to x0 mod 2^W, then, iteratively, sets

x_-N+i = [i+1812433253((x_-N+i-1>>(W -2))Λ(x_-N+i-1))] mod 2W

for i = 1 …N - 1.

The template member function seed(Gen& g) sets the object’s state to the successive values g() mod 2^W, respectively.

The template implements the Mersenne Twister algorithm. The most commonly used version of the Mersenne Twister is implemented by mt19937 (see Section 13.4.3).

The algorithm is fast, but it has a large state, requiring N*W bits of storage.^[11] An implementation typically updates all the state values at once, rather than changing them one at a time, as the algorithm specifies. This approach is faster, but it requires twice as much storage space.

13.2.3. Basic Engine subtract_with_carry

The class template describes a simple engine that produces values of type IType by applying the recurrence relation x_i = (x_i-S - x_i-R - cy_i-1) mod M, where cy_i = 1 if x_i-S - x_i-R - cy_i-1 < 0; otherwise, cy_i = 0.

The type argument IType must be an integral type large enough to hold values up to M. In addition, 0 < S < R.

The size of the engine’s state is R, and its value is the sequence of values x_i-R, …,x_i-1, cy_i-1, in that order.

The member function seed(unsigned long x0) creates a generator object, lcg, of type linear_congruential<unsigned long, 2147483563, 40014, 0>. It initalizes it with the value x0 if x0 is not zero; otherwise, with the value 19780503. It then generates successive state values x_-R,…,x_-1 with lcg() mod M, then sets cy_-1 to 1 if x_-1 is 0; otherwise, to 0.

The member function template seed(Gen& g) accumulates unsigned 32-bit values produced by calling g() to generate successive state values x_-R,…,x_-1, then sets cy_-1 to 1 if x_-1 is 0, otherwise to 0. Formally, with N=⌊(M+31)/32⌋, the function uses g() to generate N*R successive values Z₀,Z₁,…,Z_N*R-1 and initializes the engine’s state x_-R,…,x_-1 to the values (Z₀· 2⁰+· · · +Z_N-1· 2³²(N-1)) mod M, …,(Z_N*R-N 2⁰+… +Z_N*R-1 2³²(N-1)) mod M.

The engine generates values without multiplication, so it is quite fast.^[12] With suitable lags, it generates pretty good random sequences. It can be improved significantly by discarding some of the generated values, as done by ranlux3(see Section 13.4.4) and ranlux4 (see Section 13.4.5).

13.2.4. Basic Engine subtract_with_carry_01

The class template describes a simple engine that produces values of type RType by applying the recurrence relation x_i = (x_i—S - x_i—R - cy_i—1⁾ mod 1, where cy_i = 2^-W if x_i—S - x_i—R - cy_i—1 < 0; otherwise, cy_i = 0.

The type argument RType must be a floating-point type with enough precision to hold all the bits in the generated values. In addition, 0 < S < R.

The size of the engine’s state is R. With N = |(W + 31)/32 |, each value x_i-k can be represented as (z_k,0 + z_k,1 ·2³² + … + z_k,N—1 ·2^{32 (N-1)})/2^W. The textual representation of the state is the textual representation of the values z_R,0, …,z_R,N-1, …,z_1,0, …,z_1,N-1,cy_i-1 ·2^W.

The member function seed(unsigned long x0) creates a generator object, lcg, of type linear_congruential<unsigned long, 2147483563, 40014, 0>. It initalizes it with the value x0 if x0 is not zero; otherwise, with the value 19780503. It then generates successive state values x_-R, …,x_-1 with lcg()· 2^—W mod 1, then sets cy_-1 to 2^-W if x_-1 is 0; otherwise, to 0.

The member function template seed(Gen& g) accumulates unsigned 32-bit values produced by calling g() to generate successive state values x_-R, …,x_-1, then sets cy_-1 to 2^-W if x_-1 is 0, otherwise to 0. Formally, with N=⌊(M+31)/32⌋, the function uses g() to generate N*R successive values Z₀,Z₁,…,Z_N*R-1 and initializes the engine’s state x_-R,…,x_-1 to the values (Z₀·2⁰+· · ·+Z_N-1·2³²(^N-¹⁾)·2^-W mod 1,…,(Z_N*R-N ·2⁰+· · · +Z_N*R-1 2^32(N-1)) 2^-W mod 1.

The engine generates floating-point values in the range [0.0, 1.0). If you wade through the details of the specification, you’ll see that with a binary floating-point implementation, the returned values have no more than W bits in their fraction. Other floating-point representations may need more bits but must return the same values as the binary representation.

Just like subtract_with_carry, this algorithm is quite fast. Its predefined versions are ranlux_base_01 (Section 13.4.6) and ranlux64_base_01(Section 13.4.7). Also like subtract_with_carry, with suitable lags, it generates pretty good random sequences, which can be improved by discarding some of the values, as done by ranlux3_01 (see Section 13.4.8) and ranlux4_01 (see Section 13.4.9).

13.2.5. Compound Engine discard_block

The class template describes a compound engine whose operator() returns the first P values returned by the engine eng, then discards the next P - R values returned by eng, and then repeats this cycle as necessary.

The type argument Eng must be an engine type that satisfies the requirements set out at the beginning of this chapter. In addition, 0 < R <= P.^[13]

The size of the engine’s state is one more than the size of eng’s state. Its textual representation is the textual representation of eng, followed by the textual representation of the number of calls to operator() since the beginning of the current cycle.

The engine can sometimes be used to improve the quality of another engine.^[14] See, for example, ranlux3 (Section 13.4.4), ranlux4 (Section 13.4.5), ranlux3_01 (Section 13.4.8), and ranlux4_01 (Section 13.4.9).

13.2.6. Compound Engine xor_combine

The class template describes a compound engine whose operator() returns (eng1() << shift1) Λ (eng2() << shift2).

The type arguments Eng1 and Eng2 must be engine types that satisfy the requirements set out at the beginning of this chapter. Each type’s nested member typedef result_type must be an integral type. The template’s nested type xor_combine::result_type is the one of those two nested types that provides the most storage. In addition, 0 <= s1 and 0 <= s2.

The size of the engine’s state is the sum of the sizes of the states of eng1 and eng2. Its textual representation is the textual representation of eng1, followed by the textual representation of eng2.

The engine combines the results of two engines, using left shifts and bitwise exclusive OR. Except in unusual circumstances, at least one of the two shift values should be 0. For best results, the engine whose value is not shifted should produce values ranging from 0 to 2ⁿ - 1, and the shifted values from the other engine should be somewhere in that range.

13.3. TR1 Library Class random_device

This class draws random numbers from a system-supplied source, if there is one.

The class describes an engine that produces nondeterministic sequences of random numbers on platforms on which this can be done. On platforms on which this can’t be done, it uses an unspecified random number generator.

The default value and the meaning of the constructor argument token are defined by the implementation. The constructor throws an exception object of a type that is derived from std::exception if the random_-device object cannot be initialized.

The member functions min and max return the values 0 and numeric_-limits<result_type>::max(), respectively.

The member function operator() returns a random value. The returned values are uniformly distributed in the closed range [min(), max()]. The operator throws an exception object of a type that is derived from std:: exception if a random number cannot be obtained.

The member function entropy returns a value between min() and the base 2 logarithm of (max() + 1) that represents an estimate of the entropy of the random numbers. If the class uses a random number generator, the function returns 0.

13.4. Predefined Engines in the TR1 Library

The TR1 library provides nine predefined engines. These engines, in the form of typedefs for particular template specializations, represent some of the most commonly used random number generators. For most of the predefined engines, the specification gives the ten-thousandth value returned by the function call operator for a default constructed object. This value can be used to check whether the template and the specialization have been implemented correctly.

13.4.1. minstd_rand0

The type uint is an implementation-defined unsigned integral type, large enough to hold values in the range [0, 2147483657].

x_10,000 = 1,043,618,065.

13.4.2. minstd_rand

The type uint is an implementation-defined unsigned integral type, large enough to hold values in the range [0, 2147483657].

x_10,000 = 399,268,537.

13.4.3. mt19937

The type uint is an implementation-defined unsigned integral type that is at least 32 bits wide.

x_10,000 = 4,123,659,995.

13.4.4. ranlux3

The type sint is an implementation-defined signed integral type with at least 24 value bits.

x_10,000 = 5,957,620.

13.4.5. ranlux4

The type sint is an implementation-defined signed integral type with at least 24 value bits.

x_10,000 = 8,587,295.

13.4.6. ranlux_base_01

13.4.7. ranlux64_base_01

13.4.8. ranlux3_01

x_10,000 = 5,957,620.2^-24.

13.4.9. ranlux4_01

x_10,000 = 8,587,295.2^-24.

13.5. Random Number Distributions

A random number distribution is a class or a template whose objects transform a stream of uniformly distributed random numbers obtained from an engine into a stream of random numbers with a particular distribution. Distributions can be either discrete or continuous. A discrete distribution describes random numbers chosen from a countable set of possible values. Although the size of that set can be infinite, it is much more common for it to be finite. The most obvious example is tossing a coin; the set of possible values is heads and tails. Discrete distributions in the TR1 library return integer values. A continuous distribution describes random numbers chosen from a continuous range of possible values. For example, the time between particle emissions in radioactive decay is random, with an exponential distribution. Continuous distributions in the TR1 library return floating-point values.^[15]

A random number distribution that conforms to the TR1 library specification provides only a few fundamental operations: You can get the next value in the random sequence, discard any internal state values that the distribution may be using, write the state of a distribution to an output stream with a stream inserter, and read the state from an input stream with a stream extractor.

Example 13.3. Basic Properties (random/distprops.cpp)

More formally, for every distribution type Dist and object dist of type Dist, the following expressions must be valid.

Getting Values

• Dist::input_type: the typedef is a synonym for the type that the engine passed to the distribution’s operator() must return.

• Dist::result_type: the typedef is a synonym for the type returned by the distribution’s operator().

• dist(gen): repeated invocations of the expression produce a sequence of random values distributed according to the definition of the particular distribution. The object gen must be an object of a type that implements the requirements for a generator, and the expression gen() must return values of type Dist::input_type. If Dist::input_type is a floating-point type, the expression gen() must return values in the closed range [0.0, 1.0].^[16]

Reading, Writing, and Resetting

• os << dist: writes the state of dist to the output stream os.

• is >> dist1: reads the new state of dist1 from the input stream is.^[17]

• dist.reset(): discards any internal state that the distribution maintains.

The TR1 library specification does not have any requirements for states of distributions,^[18] and many distributions do not have any internal state. Still, it’s a good habit to always call reset when you’ve been using a distribution object with one engine object and change to a different engine object or reseed the original engine object. That will ensure that you discard any leftovers from the previous engine.

The distributions in the TR1 library all have member functions that return the values of the arguments passed to an object’s constructor. This is not required for distributions in general. However, it’s a good idea to do the same in distributions that you write.

13.6. Discrete Distributions

The specifications for the discrete distributions in the TR1 library give the probability of each possible value. The formula p(i)= … means that the probability of getting the value i is given by the expression on the right-hand side of the equals sign.

13.6.1. bernoulli_distribution

p(T)= P

p(F)= 1 - P

The value of the constructor argument P0 must be in the closed range [0.0, 1.0]. In a call to operator() on a bernoulli_distribution object, the type Eng of the argument eng must be an engine whose operator() returns int.

Instances of the template bernoulli_distribution produce sequences of random values true and false, with the probability of true equal to the stored value P.

13.6.2. binomial_distribution

The value of the constructor argument T0 must be greater than or equal to 0. The value of the constructor argument P0 must be in the closed range [0.0, 1.0]. In a call to operator() on a binomial_distribution object, the type Eng of the argument eng must be an engine whose operator() returns int.

Instances of the template binomial_distribution produce random sequences of values of type IType in the closed range [0, T]. For an event whose probability of success is P, each value I in the random sequence occurs with probability equal to the probability of getting success exactly I times in T trials.

13.6.3. geometric_distribution

p(i)=(1-P) P^i-1

The value of the constructor argument P0 must be in the open range (0.0, 1.0). In a call to operator() on a geometric_distribution object, the type Eng of the argument eng must be an engine whose operator() returns RType.

Instances of the template geometric_distribution produce sequences of random values of type IType, all of which are greater than or equal to 1. For an event whose probability of success is P, each value I in the random sequence occurs with probability equal to the probability of getting the first success on the Ith trial.

13.6.4. poisson_distribution

The value of the constructor argument M0 must be greater than 0. In a call to operator() on a poisson_distribution object, the type Eng of the argument eng must be an engine whose operator() returns RType.

Instances of the template poisson_distribution produce random sequences of values of type IType, all of which are greater than or equal to 0. For an event that occurs at intervals whose average duration is M, each value I in the random sequence occurs with probability equal to the probability that I events will occur in an interval of duration M.

13.6.5. uniform_int

The value of the constructor argument min0 must be less than or equal to the value of the constructor argument max0. In a call to operator() on a uniform_int object, the type Eng of the argument eng must be an engine whose operator() returns IType.

The values returned by calls to operator()(eng) will be uniformly distributed in the closed range [N, X]. The values returned by calls to operator()(eng, val) will be uniformly distributed in the half-open range [0, val).

Instances of the template uniform_int produce uniformly distributed random sequences of values of type IType, all of whose values are greater than or equal to the specified minimum value and less than or equal to the specified maximum value. Further, the function call operator that takes two arguments produces random sequences all of whose values are greater than or equal to the specified minimum value and strictly less than the value of the second argument.^[19]

13.7. Continuous Distributions

The specifications for the continuous distributions in the TR1 library give the probability density function for the distribution. Given a probability density function p(x), the probability that a result will be in the closed range [a,b] is .

As mentioned earlier, the engine that you pass to the function call operator of a continuous distribution must return values in the closed range [0.0, 1.0].

13.7.1. exponential_distribution

p(x)= λe^-λx

The stored value L is the value of λ in the probability density function p(x).

The value of the constructor argument L0 must be greater than 0. In a call to operator() on an exponential_distribution object, the type Eng of the argument eng must be an engine whose operator() returns RType.

Instances of the template exponential_distribution produce random sequences of values of type Rtype, all of which are greater than 0. For a process whose state changes at intervals whose average duration is L, values within the random sequence in the interval x,x + Δx occur with probability equal to the probability that the process will change state within an interval whose duration is between x and x + Δx.

13.7.2. gamma_distribution

The stored value A is the value of α in the probability density function p(x).

The value of the constructor argument A0 must be greater than 0. In a call to operator() on a gamma_distribution object, the type Eng of the argument eng must be an engine whose operator() returns RType.

Instances of the template gamma_distribution produce random sequences of values of type Rtype, all of which are greater than 0. For a process whose state changes at intervals whose average duration is 1, and when A is an integer, values within the random sequence in the interval x,x + Δx occur with probability equal to the probability that the process will change state A times within an interval whose duration is between x and x + Δx.^[20] Thus, values in the sequence generated by an instance of the template gamma_distribution with A == 1 will have the same distribution as values in the sequence generated by an instance of the template exponential_distribution with L == 1.

13.7.3. normal_distribution

The stored value S is the values of σ in the probability density function p(x).

The value of the constructor argument S0 must be greater than 0. In a call to operator() on a normal_distribution object, the type Eng of the argument eng must be an engine whose operator() returns RType.

Instances of the template normal_distribution produce random sequences of values of type RType. The values occur with probabilities given by the normal distribution with mean value M and variance S*S.

13.7.4. uniform_real

The value of the constructor argument min0 must be less than the value of the constructor argument max0.^[21] In a call to operator() on a uniform_-real object, the type Eng of the argument eng must be an engine whose operator() returns RType.

The values returned by calls to operator()(eng) will be uniformly distributed in the half-open range [N,X).

Instances of the template uniform_real produce uniformly distributed random sequences of values of type RType, all of whose values are greater than or equal to the specified minimum value and less than the specified maximum value.

13.8. The variate_generator Class Template

As we’ve seen, the generator object that you pass to a distribution’s operator() must return the exact type that the distribution expects. In addition, when that type is a floating-point type, the values returned by the generator must be in the closed range [0.0, 1.0]. If you need to use a generator that doesn’t meet these constraints, or if you want to consolidate a generator and a distribution into a single object, use the class template variate_generator.

The template type argument Generator must name a generator type, Gen, or a pointer or reference to a generator type, Gen* or Gen&. The nested typedef engine_value_type is a synonym for the underlying generator type Gen.

The class template effectively creates a wrapper object WG that transforms the values returned by G() as follows:

• If Gen::result_type and Dist::result_type are both integral types, WG() returns G().

• If Gen::result_type is an integral type and Dist::result_type is a floating-point type, WG() returns Dist::result_type(G())/ (G.max() - G.min() + 1).

• If Dist::result_type is an integral type and Gen::result_type is a floating-point type, WG() returns the result of an implementation-defined transformation of G().

• If Gen::result_type and Dist::result_type are both floating-point types, WG() returns Dist::result_type(G()) / (G.max() - G.min()).

The member operator()() returns D(WG). The member operator()(T value) returns D(WG, value).

To combine an engine and a generator, you pass the type of the engine and the type of the distribution as arguments to the variate_generator template. Then you create a variate_generator object, passing an engine object and a distribution object to the constructor. Once you’ve created a variate_generator object, you can manipulate its stored engine and distribution objects directly through the member functions engine and distribution.

Example 13.4. Simple variate_generator Object (random/variate.cpp)

In Part 1 of the preceding example, note that the pairs of values displayed in each line are the same. The engines and distributions used by dist(eng) and gen start in the same state, so they generate the same sequence of values. Part 2 reseeds both engines and resets both distributions, so they again produce the same pairs of values.

You can also create a variate_generator object that holds a pointer or a reference to its engine.

Example 13.5. variate_generator with Reference (random/varref.cpp)

In Part 1 of this example, note that the pairs of values are not the same. That’s because the engine argument to the variate_generator instantiation is a reference to eng_t instead of simply eng_t. As a result, the gen object holds a reference to eng instead of a copy of it. The calls to dist(eng) change the state of eng, and the subsequent calls to gen() use its new state. To get the same sequence as we got with dist(eng), we have to reseed eng, as shown in Part 2.

The two preceding examples have simply encapsulated an engine and a distribution. The code to generate sequences of random numbers is slightly simpler, because you don’t have to pass an engine to the distribution; the variate_generator template takes care of that.

In addition, when you use variate_generator, you don’t have to match the engine’s result_type to the distribution’s input_type, and, when the distribution takes a floating-point type, you aren’t restricted to engines that generate values in the closed range [0.0, 1.0].

Example 13.6. Matching Type and Range with variate_generator (random/varmatch.cpp)

Further Reading

• The Art of Computer Programming [Knu98a, 1–193] is, as usual, an outstanding reference.

• Numerical Recipes in C [PTVF92] has implementations of several engines and distributions.

• e-Handbook of Statistical Methods, section 1.3.6.6” [NIS] has information on many statistical distributions. See www.itl.nist.gov/div898/handbook/eda/section3/eda366.htm.

Exercises

Exercise 1

1. Create an engine object that applies the recurrence relation x_i =(2.x_i-1 + 1) mod 6. Seed the object with the value 0, and generate a sequence of several thousand elements, counting the number of times each value occurs. Try it two more times, with seeds of 1 and 2. Would you bet your life on this roll?

2. Does picking a multiplier and modulus that are relatively prime improve this engine? Create an engine object that applies the recurrence relation x_i =(5 x_i-1 + 1) mod 6, and repeat the previous test.

3. Does picking a modulus that is a prime number improve this engine? Create an engine object that applies the recurrence relation x_i =(2.x_i-1 + 1) mod 7, and repeat the previous test.

Exercise 2

Write a typedef for a subtract_with_carry instantiation with a modulus of 6, a short lag of 4, and a long lag of 7. It should return values of type int.^[22]

1. Create an object of this type with the default constructor, and examine the first few values that it generates.

2. Call seed() on the object in the previous part, and verify that the first few values generated by the engine are the same as before.

3. Write a function that takes no arguments and returns values of type unsigned int. Successive calls to this function should return the values 0, 1, 2, and so on. Use this function to seed the engine, and examine the first few values that the engine generates.

4. Write a class template that takes one type argument named InIt. The class should store two values of that type, named first and last, and should have a constructor that takes two arguments of that type and copies them to first and last. The class should also have an operator() that returns values of type std::iterator_-traits<InIt>::value_type,^[23] with the following properties.

a. If first == last, it should throw an exception of type std ::length_error.

b. Otherwise, it should return *first++.

Using std::vector, create an object named seeds that holds seven unsigned int values such that seeds[i] == i for i ranging from 0 to 6. Use your class template to create an object that holds begin and end iterators to this vector object. Use that object to seed the engine, and verify that the first few values generated by the engine are the same as before.

Exercise 3

Write a program that uses floating-point values from one of the predefined engines to generate values in the closed range [0, 1]. Generate several thousand values, and show the frequency of each of the generated values.

Exercise 4

Write a program that (a) creates an object whose type is one of the predefined engines that generates integer values and (b) creates an object of type bernoulli_distribution that returns true with probability one-half. Use the engine object as the source of random values for the generator to generate several thousand values, and show the frequency of each of the resulting values.

Exercise 5

Write a program that (a) creates an object whose type is one of the predefined engines that generates integer values and (b) creates an object whose type is an instantiation of uniform_int that generates values in the closed range [0, 1]. Use the engine object as the source of random values for the generator to generate several thousand sets of four values and adds the four values in each set together. Show the frequency of each of the resulting values.

Exercise 6

Write a program that (a) creates an object whose type is one of the predefined engines that generates integer values and (b) creates an object whose type is an instantiation of binomial_distribution that generates values in the closed range [0, 4], with a probability of success of one-half. Combine the engine and the generator, using variate_generator. Generate several thousand values, and show the frequency of each of the resulting values.