...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Random numbers are required in a number of different problem domains, such as
The Boost Random Number Generator Library provides a framework for random number generators with welldefined properties so that the generators can be used in the demanding numerics and security domains. For a general introduction to random numbers in numerics, see
"Numerical Recipes in C: The art of scientific computing", William H. Press, Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd ed., 1992, pp. 274328
Depending on the requirements of the problem domain, different variations of random number generators are appropriate:
All variations have some properties in common, the concepts (in the STL sense) is called UniformRandomNumberGenerator. This concept will be defined in a subsequent section.
The goals for this library are the following:
A uniform random number generator provides a sequence of random numbers uniformly distributed on a given range. The range can be compiletime fixed or available (only) after runtime construction of the object.
The tight lower bound of some (finite) set S is the (unique) member l in S, so that for all v in S, l <= v holds. Likewise, the tight upper bound of some (finite) set S is the (unique) member u in S, so that for all v in S, v <= u holds.
In the following table, X denotes a number generator class returning objects of type T, and v is a const value of X.
Table 25.1. UniformRandomNumberGenerator requirements
expression 
return type 
pre/postcondition 






 


tight lower bound on the set of all values returned by 


if 
The member functions min
,
max
, and operator()
shall have amortized constant time complexity.
Note  

For integer generators (i.e. integer Rationale: The range description with min and max serves two purposes. First, it allows scaling of the values to some canonical range, such as [0..1). Second, it describes the significant bits of the values, which may be relevant for further processing. The range is a closed interval [min,max] for integers, because the underlying type may not be able to represent the halfopen interval [min,max+1). It is a halfopen interval [min, max) for nonintegers, because this is much more practical for borderline cases of continuous distributions. 
Note  

The UniformRandomNumberGenerator
concept does not require
Rationale: 
A nondeterministic uniform random number generator is a UniformRandomNumberGenerator that is based on some stochastic process. Thus, it provides a sequence of trulyrandom numbers. Examples for such processes are nuclear decay, noise of a Zehner diode, tunneling of quantum particles, rolling a die, drawing from an urn, and tossing a coin. Depending on the environment, interarrival times of network packets or keyboard events may be close approximations of stochastic processes.
The class random_device
is a model for a nondeterministic random number generator.
Note  

This type of randomnumber generator is useful for security applications, where it is important to prevent an outside attacker from guessing the numbers and thus obtaining your encryption or authentication key. Thus, models of this concept should be cautious not to leak any information, to the extent possible by the environment. For example, it might be advisable to explicitly clear any temporary storage as soon as it is no longer needed. 
A pseudorandom number generator is a UniformRandomNumberGenerator
which provides a deterministic sequence of pseudorandom numbers, based
on some algorithm and internal state. Linear
congruential
and inversive
congruential
generators are examples of such pseudorandom
number generators. Often, these generators are very sensitive to
their parameters. In order to prevent wrong implementations from being
used, an external testsuite should check that the generated sequence and
the validation value provided do indeed match.
Donald E. Knuth gives an extensive overview on pseudorandom number generation in his book "The Art of Computer Programming, Vol. 2, 3rd edition, AddisonWesley, 1997". The descriptions for the specific generators contain additional references.
Note  

Because the state of a pseudorandom number generator is necessarily finite, the sequence of numbers returned by the generator will loop eventually. 
In addition to the UniformRandomNumberGenerator
requirements, a pseudorandom number generator has some additional requirements.
In the following table, X
denotes a pseudorandom number generator class, u
is a value of X
, i
is a value of integral type, s
is a value of a type which models
SeedSeq,
and j
a value of type
unsigned long
long
.
Table 25.2. PseudoRandomNumberGenerator requirements
expression 
return type 
pre/postcondition 


 
creates a generator with a default seed. 

 
creates a generator seeding it with the integer 

 
creates a generator setting its initial state from the SeedSeq



sets the current state to be identical to the state that would be created by the corresponding constructor. 


Advances the generator by 
Classes which model a pseudorandom number generator shall also model
EqualityComparable,
i.e. implement operator==
.
Two pseudorandom number generators are defined to be equivalent
if they both return an identical sequence of numbers starting from a given
state.
Classes which model a pseudorandom number generator shall also model the
Streamable concept, i.e. implement operator<<
and operator>>
. operator<<
writes all current state of the
pseudorandom number generator to the given ostream
so that operator>>
can restore the state at a later time. The state shall be written in a
platformindependent manner, but it is assumed that the locales
used for writing and reading be the same. The pseudorandom number generator
with the restored state and the original at the justwritten state shall
be equivalent.
Classes which model a pseudorandom number generator should also model the CopyConstructible and Assignable concepts. However, note that the sequences of the original and the copy are strongly correlated (in fact, they are identical), which may make them unsuitable for some problem domains. Thus, copying pseudorandom number generators is discouraged; they should always be passed by (nonconst) reference.
The classes rand48
,
minstd_rand
, and
mt19937
are models
for a pseudorandom number generator.
Note  

This type of randomnumber generator is useful for numerics, games and
testing. The nonzero arguments constructor(s) and the 
A SeedSeq represents a sequence of values that can be used to set the initial
state of a PseudoRandomNumberGenerator.
i
and j
are RandomAccessIterators whose value_type
is an unsigned integer type with at least 32 bits.
Table 25.3. SeedSeq requirements
expression 
return type 
pre/postcondition 
complexity 


void 
stores 32bit values to all the elements in the iterator range
defined by 
O(j  i) 
The class seed_seq
and every UniformRandomNumberGenerator
provided by the library are models of SeedSeq.
A random distribution produces random numbers distributed according to
some distribution, given uniformly distributed random values as input.
In the following table, X
denotes a random distribution class returning objects of type T
, u
is a value of X
, x
and y
are (possibly const) values of X
,
P
is the param_type
of the distribution, p
is a value of P
,
and e
is an lvalue of an
arbitrary type that meets the requirements of a UniformRandomNumberGenerator,
returning values of type U
.
Table 25.4. Random distribution requirements (in addition to CopyConstructible, and Assignable)
expression 
return type 
pre/postcondition 
complexity 



 
compiletime 


A type that stores the parameters of the distribution, but not
any of the state used to generate random variates. 
compiletime 


Initializes a distribution from its parameters 
O(size of state) 


subsequent uses of 
constant 


the sequence of numbers returned by successive invocations with
the same object 
amortized constant number of invocations of 


Equivalent to X(p)(e), but may use a different (and presumably more efficient) implementation 
amortized constant number of invocations of 


Returns the parameters of the distribution 
O(size of state) 

void 
Sets the parameters of the distribution 
O(size of state) 


returns the minimum value of the distribution 
constant 


returns the maximum value of the distribution 
constant 


Indicates whether the two distributions will produce identical sequences of random variates if given equal generators 
O(size of state) 



O(size of state) 


writes a textual representation for the parameters and additional
internal data of the distribution 
O(size of state) 


restores the parameters and additional internal data of the distribution

O(size of state) 
Additional requirements: The sequence of numbers produced by repeated invocations
of x(e)
does
not change whether or not os
<< x
is invoked between any of the invocations x(e)
.
If a textual representation is written using os
<< x
and that representation is restored into the same or a different object
y
of the same type using
is >>
y
, repeated invocations of y(e)
produce the same sequence of random numbers
as would repeated invocations of x(e)
.
This library provides several pseudorandom
number generators. The quality of a pseudo
random number generator crucially depends on both the algorithm and
its parameters. This library implements the algorithms as class templates
with template value parameters, hidden in namespace
boost::random
. Any particular choice of parameters
is represented as the appropriately specializing typedef
in namespace boost
.
Pseudorandom number generators should not be constructed (initialized) frequently during program execution, for two reasons. First, initialization requires full initialization of the internal state of the generator. Thus, generators with a lot of internal state (see below) are costly to initialize. Second, initialization always requires some value used as a "seed" for the generated sequence. It is usually difficult to obtain several good seed values. For example, one method to obtain a seed is to determine the current time at the highest resolution available, e.g. microseconds or nanoseconds. When the pseudorandom number generator is initialized again with the thencurrent time as the seed, it is likely that this is at a nearconstant (nonrandom) distance from the time given as the seed for first initialization. The distance could even be zero if the resolution of the clock is low, thus the generator reiterates the same sequence of random numbers. For some applications, this is inappropriate.
Note that all pseudorandom
number generators described below are CopyConstructible
and Assignable. Copying
or assigning a generator will copy all its internal state, so the original
and the copy will generate the identical sequence of random numbers. Often,
such behavior is not wanted. In particular, beware of the algorithms from
the standard library such as std::generate
.
They take a functor argument by value, thereby invoking the copy constructor
when called.
The following table gives an overview of some characteristics of the generators. The cycle length is a rough estimate of the quality of the generator; the approximate relative speed is a performance measure, higher numbers mean faster random number generation.
Table 25.5. generators
generator 
length of cycle 
approx. memory requirements 
approx. speed compared to fastest 
comment 

2^{31}2 

16% 
 

2^{31}2 

16% 
 

2^{48}1 

64% 
 

approx. 2^{61} 

7% 
 

? 

12% 
 

? 

37% 
 

~2^{88} 

100% 
 

2^{31}1 

2% 
good uniform distribution in several dimensions 

2^{11213}1 

100% 
good uniform distribution in up to 350 dimensions 

2^{19937}1 

93% 
good uniform distribution in up to 623 dimensions 

2^{19937}1 

38% 
good uniform distribution in up to 311 dimensions 

~2^{32000} 

59% 
 

~2^{67000} 

59% 
 

~2^{120000} 

61% 
 

~2^{170000} 

62% 
 

~2^{230000} 

59% 
 

~2^{510000} 

61% 
 

~2^{1050000} 

59% 
 

~2^{1200000} 

61% 
 

~2^{2300000} 

59% 
 

~10^{171} 

5% 
 

~10^{171} 

3% 
 

~10^{171} 

5% 
 

~10^{171} 

3% 
 

~10^{171} 

5% 
 

~10^{171} 

3% 
 

~10^{171} 

5% 
 

~10^{171} 

3% 
 

~10^{171} 

5% 
 

~10^{171} 

3% 
 
As observable from the table, there is generally a quality/performance/memory tradeoff to be decided upon when choosing a randomnumber generator. The multitude of generators provided in this library allows the application programmer to optimize the tradeoff with regard to his application domain. Additionally, employing several fundamentally different random number generators for a given application of Monte Carlo simulation will improve the confidence in the results.
If the names of the generators don't ring any bell and you have no idea which
generator to use, it is reasonable to employ mt19937
for a start: It is fast and has acceptable quality.
Note  

These random number generators are not intended for use in applications
where nondeterministic random numbers are required. See 
In addition to the random number generators, this library provides distribution functions which map one distribution (often a uniform distribution provided by some generator) to another.
Usually, there are several possible implementations of any given mapping. Often, there is a choice between using more space, more invocations of the underlying source of random numbers, or more timeconsuming arithmetic such as trigonometric functions. This interface description does not mandate any specific implementation. However, implementations which cannot reach certain values of the specified distribution or otherwise do not converge statistically to it are not acceptable.
Table 25.6. Uniform Distributions
distribution 
explanation 
example 

discrete uniform distribution on a small set of integers (much smaller than the range of the underlying generator) 
drawing from an urn 

discrete uniform distribution on a set of integers; the underlying generator may be called several times to gather enough randomness for the output 
drawing from an urn 

continuous uniform distribution on the range [0,1); important basis for other distributions 
 

continuous uniform distribution on some range [min, max) of real numbers 
for the range [0, 2pi): randomly dropping a stick and measuring its angle in radians (assuming the angle is uniformly distributed) 
Table 25.7. Bernoulli Distributions
distribution 
explanation 
example 

Bernoulli experiment: discrete boolean valued distribution with configurable probability 
tossing a coin (p=0.5) 

counts outcomes of repeated Bernoulli experiments 
tossing a coin 20 times and counting how many front sides are shown 

measures distance between outcomes of repeated Bernoulli experiments 
throwing a die several times and counting the number of tries until a "6" appears for the first time 

Counts the number of failures of repeated Bernoulli experiments required to get some constant number of successes. 
flipping a coin and counting the number of heads that show up before we get 3 tails 
Table 25.8. Poisson Distributions
distribution 
explanation 
example 

poisson distribution 
counting the number of alpha particles emitted by radioactive matter in a fixed period of time 

exponential distribution 
measuring the interarrival time of alpha particles emitted by radioactive matter 

gamma distribution 
 

weibull distribution 
 

extreme value distribution 
 

beta distribution 
 

laplace distribution 
 
Table 25.9. Normal Distributions
distribution 
explanation 
example 

counts outcomes of (infinitely) repeated Bernoulli experiments 
tossing a coin 10000 times and counting how many front sides are shown 

lognormal distribution (sometimes used in simulations) 
measuring the job completion time of an assembly line worker 

chisquared distribution 
 

Cauchy distribution 
 

Fisher F distribution 
 

Student t distribution 
 
Table 25.10. Sampling Distributions
distribution 
explanation 
example 

discrete distribution with specific probabilities 
rolling an unfair die 

 
 

 
 
Table 25.11. Miscellaneous Distributions
distribution 
explanation 
example 

triangle distribution 
 

uniform distribution on a unit sphere of arbitrary dimension 
choosing a random point on Earth (assumed to be a sphere) where to spend the next vacations 
namespace boost { namespace random { template<typename MLCG1, typename MLCG2> class additive_combine_engine; typedef additive_combine_engine< linear_congruential_engine< uint32_t, 40014, 0, 2147483563 >, linear_congruential_engine< uint32_t, 40692, 0, 2147483399 >> ecuyer1988; } }
namespace boost { namespace random { template<typename RealType = double> class bernoulli_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class beta_distribution; } }
namespace boost { namespace random { template<typename IntType = int, typename RealType = double> class binomial_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class cauchy_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class chi_squared_distribution; } }
namespace boost { namespace random { template<typename UniformRandomNumberGenerator, std::size_t p, std::size_t r> class discard_block_engine; } }
namespace boost { namespace random { template<typename IntType = int, typename WeightType = double> class discrete_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class exponential_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class extreme_value_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class fisher_f_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class gamma_distribution; } }
namespace boost { namespace random { template<typename IntType = int, typename RealType = double> class geometric_distribution; } }
namespace boost { namespace random { template<typename Engine, std::size_t w, typename UIntType> class independent_bits_engine; } }
namespace boost { namespace random { template<typename IntType, IntType a, IntType b, IntType p> class inversive_congruential_engine; typedef inversive_congruential_engine< uint32_t, 9102, 214748364736884165, 2147483647 > hellekalek1995; } }
namespace boost { namespace random { template<typename UIntType, int w, unsigned int p, unsigned int q> class lagged_fibonacci_engine; template<typename RealType, int w, unsigned int p, unsigned int q> class lagged_fibonacci_01_engine; typedef lagged_fibonacci_01_engine< double, 48, 607, 273 > lagged_fibonacci607; typedef lagged_fibonacci_01_engine< double, 48, 1279, 418 > lagged_fibonacci1279; typedef lagged_fibonacci_01_engine< double, 48, 2281, 1252 > lagged_fibonacci2281; typedef lagged_fibonacci_01_engine< double, 48, 3217, 576 > lagged_fibonacci3217; typedef lagged_fibonacci_01_engine< double, 48, 4423, 2098 > lagged_fibonacci4423; typedef lagged_fibonacci_01_engine< double, 48, 9689, 5502 > lagged_fibonacci9689; typedef lagged_fibonacci_01_engine< double, 48, 19937, 9842 > lagged_fibonacci19937; typedef lagged_fibonacci_01_engine< double, 48, 23209, 13470 > lagged_fibonacci23209; typedef lagged_fibonacci_01_engine< double, 48, 44497, 21034 > lagged_fibonacci44497; } }
namespace boost { namespace random { template<typename RealType = double> class laplace_distribution; } }
namespace boost { namespace random { template<typename IntType, IntType a, IntType c, IntType m> class linear_congruential_engine; class rand48; typedef linear_congruential_engine< uint32_t, 16807, 0, 2147483647 > minstd_rand0; typedef linear_congruential_engine< uint32_t, 48271, 0, 2147483647 > minstd_rand; } }
namespace boost { namespace random { template<typename UIntType, int w, int k, int q, int s> class linear_feedback_shift_engine; } }
namespace boost { namespace random { template<typename RealType = double> class lognormal_distribution; } }
namespace boost { namespace random { template<typename UIntType, std::size_t w, std::size_t n, std::size_t m, std::size_t r, UIntType a, std::size_t u, UIntType d, std::size_t s, UIntType b, std::size_t t, UIntType c, std::size_t l, UIntType f> class mersenne_twister_engine; typedef mersenne_twister_engine< uint32_t, 32, 351, 175, 19, 0xccab8ee7, 11, 0xffffffff, 7, 0x31b6ab00, 15, 0xffe50000, 17, 1812433253 > mt11213b; typedef mersenne_twister_engine< uint32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7, 0x9d2c5680, 15, 0xefc60000, 18, 1812433253 > mt19937; typedef mersenne_twister_engine< uint64_t, 64, 312, 156, 31, 0xb5026f5aa96619e9ull, 29, 0x5555555555555555ull, 17, 0x71d67fffeda60000ull, 37, 0xfff7eee000000000ull, 43, 6364136223846793005ull > mt19937_64; } }
namespace boost { namespace random { template<typename IntType = int, typename RealType = double> class negative_binomial_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class normal_distribution; } }
namespace boost { namespace random { template<typename RealType = double, typename WeightType = double> class piecewise_constant_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class piecewise_linear_distribution; } }
namespace boost { namespace random { template<typename IntType = int, typename RealType = double> class poisson_distribution; } }
namespace boost { namespace random { class random_device; } }
namespace boost { namespace random { template<typename URNG, typename IntType = long> class random_number_generator; } }
namespace boost { namespace random { typedef subtract_with_carry_engine< uint32_t, 24, 10, 24 > ranlux_base; typedef subtract_with_carry_01_engine< float, 24, 10, 24 > ranlux_base_01; typedef subtract_with_carry_01_engine< double, 48, 10, 24 > ranlux64_base_01; typedef discard_block_engine< ranlux_base, 223, 24 > ranlux3; typedef discard_block_engine< ranlux_base, 389, 24 > ranlux4; typedef discard_block_engine< ranlux_base_01, 223, 24 > ranlux3_01; typedef discard_block_engine< ranlux_base_01, 389, 24 > ranlux4_01; typedef discard_block_engine< ranlux64_base_01, 223, 24 > ranlux64_3_01; typedef discard_block_engine< ranlux64_base_01, 389, 24 > ranlux64_4_01; typedef subtract_with_carry_engine< uint64_t, 48, 10, 24 > ranlux64_base; typedef discard_block_engine< ranlux64_base, 223, 24 > ranlux64_3; typedef discard_block_engine< ranlux64_base, 389, 24 > ranlux64_4; typedef subtract_with_carry_engine< uint32_t, 24, 10, 24 > ranlux24_base; typedef subtract_with_carry_engine< uint64_t, 48, 5, 12 > ranlux48_base; typedef discard_block_engine< ranlux24_base, 223, 23 > ranlux24; typedef discard_block_engine< ranlux48_base, 389, 11 > ranlux48; } }
namespace boost { namespace random { class seed_seq; } }
namespace boost { namespace random { template<typename UniformRandomNumberGenerator, std::size_t k> class shuffle_order_engine; typedef shuffle_order_engine< linear_congruential_engine< uint32_t, 1366, 150889, 714025 >, 97 > kreutzer1986; typedef shuffle_order_engine< minstd_rand0, 256 > knuth_b; } }
namespace boost { namespace random { template<typename RealType = double> class student_t_distribution; } }
namespace boost { namespace random { template<typename IntType, std::size_t w, std::size_t s, std::size_t r> class subtract_with_carry_engine; template<typename RealType, std::size_t w, std::size_t s, std::size_t r> class subtract_with_carry_01_engine; } }
namespace boost { namespace random { typedef xor_combine_engine< xor_combine_engine< linear_feedback_shift_engine< uint32_t, 32, 31, 13, 12 >, 0, linear_feedback_shift_engine< uint32_t, 32, 29, 2, 4 >, 0 >, 0, linear_feedback_shift_engine< uint32_t, 32, 28, 3, 17 >, 0 > taus88; } }
namespace boost { namespace random { template<typename RealType = double> class triangle_distribution; } }
namespace boost { namespace random { template<typename RealType = double> class uniform_01; } }
namespace boost { namespace random { template<typename IntType = int> class uniform_int_distribution; } }
namespace boost { namespace random { template<typename RealType = double, typename Cont = std::vector<RealType> > class uniform_on_sphere; } }
namespace boost { namespace random { template<typename RealType = double> class uniform_real_distribution; } }
namespace boost { namespace random { template<typename IntType = int> class uniform_smallint; } }
namespace boost { template<typename Engine, typename Distribution> class variate_generator; }
namespace boost { namespace random { template<typename RealType = double> class weibull_distribution; } }
namespace boost { namespace random { template<typename URNG1, int s1, typename URNG2, int s2> class xor_combine_engine; } }