...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
random::const_mod
random::linear_congruential
rand48
random::additive_combined
random::shuffle_output
random::inversive_congruential
random::mersenne_twister
random::lagged_fibonacci
This library provides several pseudo-random 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
.
Pseudo-random 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 pseudo-random number generator is initialized again with the then-current time as the seed, it is likely that this is at a near-constant (non-random) 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 re-iterates the same sequence of random numbers. For some applications, this is inappropriate.
Note that all pseudo-random 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.
generator | length of cycle | approx. memory requirements | approx. relative speed | comment |
---|---|---|---|---|
minstd_rand |
231-2 | sizeof(int32_t) |
40 | - |
rand48 |
248-1 | sizeof(uint64_t) |
80 | - |
lrand48 (C library) |
248-1 | - | 20 | global state |
ecuyer1988 |
approx. 261 | 2*sizeof(int32_t) |
20 | - |
kreutzer1986 |
? | 1368*sizeof(uint32_t) |
60 | - |
hellekalek1995 |
231-1 | sizeof(int32_t) |
3 | good uniform distribution in several dimensions |
mt11213b |
211213-1 | 352*sizeof(uint32_t) |
100 | good uniform distribution in up to 350 dimensions |
mt19937 |
219937-1 | 625*sizeof(uint32_t) |
100 | good uniform distribution in up to 623 dimensions |
lagged_fibonacci607 |
approx. 232000 | 607*sizeof(double) |
150 | - |
lagged_fibonacci1279 |
approx. 267000 | 1279*sizeof(double) |
150 | - |
lagged_fibonacci2281 |
approx. 2120000 | 2281*sizeof(double) |
150 | - |
lagged_fibonacci3217 |
approx. 2170000 | 3217*sizeof(double) |
150 | - |
lagged_fibonacci4423 |
approx. 2230000 | 4423*sizeof(double) |
150 | - |
lagged_fibonacci9689 |
approx. 2510000 | 9689*sizeof(double) |
150 | - |
lagged_fibonacci19937 |
approx. 21050000 | 19937*sizeof(double) |
150 | - |
lagged_fibonacci23209 |
approx. 21200000 | 23209*sizeof(double) |
140 | - |
lagged_fibonacci44497 |
approx. 22300000 | 44497*sizeof(double) |
60 | - |
As observable from the table, there is generally a quality/performance/memory trade-off to be decided upon when choosing a random-number generator. The multitude of generators provided in this library allows the application programmer to optimize the trade-off 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 non-deterministic random numbers are required. See nondet_random.html for a choice of (hopefully) non-deterministic random number generators.
In this description, I have refrained from documenting those members in detail which are already defined in the concept documentation.
<boost/random.hpp>
namespace boost { namespace random { template<class IntType, IntType m> class const_mod; template<class IntType, IntType a, IntType c, IntType m, IntType val> class linear_congruential; } class rand48; typedef random::linear_congruential< /* ... */ > minstd_rand0; typedef random::linear_congruential< /* ... */ > minstd_rand; namespace random { template<class DataType, int w, int n, int m, int r, DataType a, int u, int s, DataType b, int t, DataType c, int l, IntType val> class mersenne_twister; } typedef random::mersenne_twister< /* ... */ > mt11213b; typedef random::mersenne_twister< /* ... */ > mt19937; namespace random { template<class FloatType, unsigned int p, unsigned int q> class lagged_fibonacci; } typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci607; typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci1279; typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci2281; typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci3217; typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci4423; typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci9689; typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci19937; typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci23209; typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci44497; } // namespace boost
random::const_mod
template<class IntType, IntType m> class random::const_mod { public: template<IntType c> static IntType add(IntType x); template<IntType a> static IntType mult(IntType x); template<IntType a, IntType c> static IntType mult_add(IntType x); static IntType invert(IntType x); private: const_mod(); // don't instantiate };
Class template const_mod
provides functions performing
modular arithmetic, carefully avoiding overflows. All member functions are
static; there shall be no objects of type
const_mod<>
.
The template parameter IntType
shall denote an integral
type, m
is the modulus.
Note: For modulo multiplications with large m, a trick allows fast computation under certain conditions, see
"A more portable FORTRAN random number generator", Linus Schrage, ACM Transactions on Mathematical Software, Vol. 5, No. 2, June 1979, pp. 132-138
template<IntType c> static IntType add(IntType x)
Returns: (x+c) mod m
template<IntType a> static IntType mult(IntType x)
Returns: (a*x) mod m
template<IntType a, IntType c> static IntType mult_add(IntType x)
Returns: (a*x+c) mod m
static IntType invert(IntType x)
Returns: i so that (a*i) mod m == 1
Precondition: m is prime
random::linear_congruential
#include <boost/random/linear_congruential.hpp> template<class IntType, IntType a, IntType c, IntType m, IntType val> class linear_congruential { public: typedef IntType result_type; static const IntType multiplier = a; static const IntType increment = c; static const IntType modulus = m; static const bool has_fixed_range = true; static const result_type min_value; static const result_type max_value; explicit linear_congruential_fixed(IntType x0 = 1); // compiler-generated copy constructor and assignment operator are fine void seed(IntType x0); IntType operator()(); }; typedef random::linear_congruential<long, 16807L, 0, 2147483647L, 1043618065L> minstd_rand0; typedef random::linear_congruential<long, 48271L, 0, 2147483647L, 399268537L> minstd_rand;
Instantiations of class template linear_congruential
model
a pseudo-random number
generator. Linear congruential pseudo-random number generators are
described in:
"Mathematical methods in large-scale computing units", D. H. Lehmer, Proc. 2nd Symposium on Large-Scale Digital Calculating Machines, Harvard University Press, 1951, pp. 141-146Let x(n) denote the sequence of numbers returned by some pseudo-random number generator. Then for the linear congruential generator, x(n+1) := (a * x(n) + c) mod m. Parameters for the generator are x(0), a, c, m. The template parameter
IntType
shall denote an integral
type. It must be large enough to hold values a, c, and m. The template
parameters a and c must be smaller than m.
Note: The quality of the generator crucially depends on the
choice of the parameters. User code should use one of the sensibly
parameterized generators such as minstd_rand
instead.
For each choice of the parameters a, c, m, some distinct type is defined,
so that the static
members do not interfere with regard to the
one definition rule.
explicit linear_congruential(IntType x0 = 1)
Effects: Constructs a linear_congruential
generator with x(0) := x0
.
void seed(IntType x0)
Effects: Changes the current value x(n) of the
generator to x0
.
The specialization minstd_rand0
was originally suggested
in
A pseudo-random number generator for the System/360, P.A. Lewis, A.S. Goodman, J.M. Miller, IBM Systems Journal, Vol. 8, No. 2, 1969, pp. 136-146It is examined more closely together with
minstd_rand
in
"Random Number Generators: Good ones are hard to find", Stephen K. Park and Keith W. Miller, Communications of the ACM, Vol. 31, No. 10, October 1988, pp. 1192-1201
rand48
#include <boost/random/linear_congruential.hpp> class rand48 { public: typedef int32_t result_type; static const bool has_fixed_range = true; static const int32_t min_value = 0; static const int32_t max_value = 0x7fffffff; explicit rand48(int32_t x0 = 1); explicit rand48(uint64_t x0); // compiler-generated copy ctor and assignment operator are fine void seed(int32_t x0); void seed(uint64_t x0); int32_t operator()(); };
Class rand48
models a pseudo-random number generator. It
uses the linear congruential algorithm with the parameters a = 0x5DEECE66D,
c = 0xB, m = 2**48. It delivers identical results to the
lrand48()
function available on some systems (assuming
lcong48
has not been called).
It is only available on systems where uint64_t
is provided
as an integral type, so that for example static in-class constants and/or
enum definitions with large uint64_t
numbers work.
rand48(int32_t x0)
Effects: Constructs a rand48
generator
with x(0) := (x0
<< 16) | 0x330e.
rand48(uint64_t x0)
Effects: Constructs a rand48
generator
with x(0) := x0
.
void seed(int32_t x0)
Effects: Changes the current value x(n) of the
generator to (x0
<< 16) | 0x330e.
void seed(uint64_t x0)
Effects: Changes the current value x(n) of the
generator to x0
.
random::additive_combine
#include <boost/random/additive_combine.hpp> template<class MLCG1, class MLCG2, typename MLCG1::result_type val> class random::additive_combine { public: typedef MLCG1 first_base; typedef MLCG2 second_base; typedef typename MLCG1::result_type result_type; static const bool has_fixed_range = true; static const result_type min_value = 1; static const result_type max_value = MLCG1::max_value-1; additive_combine(); additive_combine(typename MLCG1::result_type seed1, typename MLCG2::result_type seed2); result_type operator()(); bool validation(result_type x) const; }; typedef random::additive_combine< random::linear_congruential<int32_t, 40014, 0, 2147483563, 0>, random::linear_congruential<int32_t, 40692, 0, 2147483399, 0>, /* unknown */ 0> ecuyer1988;
Instatiations of class template additive_combine
model a
pseudo-random number
generator. It combines two multiplicative linear congruential number
generators, i.e. those with c = 0. It is described in
"Efficient and Portable Combined Random Number Generators", Pierre L'Ecuyer, Communications of the ACM, Vol. 31, No. 6, June 1988, pp. 742-749, 774The template parameters
MLCG1
and
MLCG2
shall denote two different linear congruential number
generators, each with c = 0. Each invocation returns a random number X(n)
:= (MLCG1(n) - MLCG2(n)) mod (m1 - 1), where m1 denotes the modulus of
MLCG1
.
The template parameter val
is the validation value checked
by validation
.
additive_combine()
Effects: Constructs an additive_combine
generator using the default constructors of the two base generators.
additive_combine(typename MLCG1::result_type seed1, typename MLCG2::result_type seed2)
Effects: Constructs an additive_combine
generator, using seed1
and seed2
as the
constructor argument to the first and second base generator,
respectively.
The specialization ecuyer1988
was suggested in the above
paper.
random::shuffle_output
#include <boost/random/shuffle_output.hpp> template<class UniformRandomNumberGenerator, int k, typename UniformRandomNumberGenerator::result_type val = 0> class random::shuffle_output { public: typedef UniformRandomNumberGenerator base_type; typedef typename base_type::result_type result_type; static const bool has_fixed_range = false; shuffle_output(); template<class T> explicit shuffle_output(T seed); explicit shuffle_output(const base_type & rng); template<class T> void seed(T s); result_type operator()(); result_type min() const; result_type max() const; bool validation(result_type) const; };
Instatiations of class template shuffle_output
model a
pseudo-random number
generator. It mixes the output of some (usually linear congruential)
uniform random number generator to get better statistical properties.
According to Donald E. Knuth, "The Art of Computer Programming, Vol. 2",
the algorithm is described in
"Improving a poor random number generator", Carter Bays and S.D. Durham, ACM Transactions on Mathematical Software, Vol. 2, 1979, pp. 59-64.The output of the base generator is buffered in an array of length k. Every output X(n) has a second role: It gives an index into the array where X(n+1) will be retrieved. Used array elements are replaced with fresh output from the base generator.
Template parameters are the base generator and the array length k, which
should be around 100. The template parameter val
is the
validation value checked by validation
.
shuffle_output()
Effects: Constructs a shuffle_output
generator by invoking the default constructor of the base generator.
Complexity: Exactly k+1 invocations of the base generator.
template<class T> explicit shuffle_output(T seed)
Effects: Constructs a shuffle_output
generator by invoking the one-argument constructor of the base generator
with the parameter seed
.
Complexity: Exactly k+1 invocations of the base generator.
explicit shuffle_output(const base_type & rng)
Precondition: The template argument
UniformRandomNumberGenerator
shall denote a CopyConstructible
type.
Effects: Constructs a shuffle_output
generator by using a copy of the provided generator.
Complexity: Exactly k+1 invocations of the base generator.
template<class T> void seed(T s)
Effects: Invokes the one-argument seed
method of the base generator with the parameter seed
and
re-initializes the internal buffer array.
Complexity: Exactly k+1 invocations of the base generator.
According to Harry Erwin (private e-mail), the specialization
kreutzer1986
was suggested in:
"System Simulation: programming Styles and Languages (International Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December 1986.
random::inversive_congruential
#include <boost/random/inversive_congruential.hpp> template<class IntType, IntType a, IntType b, IntType p> class random::inversive_congruential { public: typedef IntType result_type; static const bool has_fixed_range = true; static const result_type min_value = (b == 0 ? 1 : 0); static const result_type max_value = p-1; static const result_type multiplier = a; static const result_type increment = b; static const result_type modulus = p; explicit inversive_congruential(IntType y0 = 1); void seed(IntType y0); IntType operator()(); }; typedef random::inversive_congruential<int32_t, 9102, 2147483647-36884165, 2147483647> hellekalek1995;
Instantiations of class template inversive_congruential
model a pseudo-random number
generator. It uses the inversive congruential algorithm (ICG) described
in
"Inversive pseudorandom number generators: concepts, results and links", Peter Hellekalek, In: "Proceedings of the 1995 Winter Simulation Conference", C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman (editors), 1995, pp. 255-262. ftp://random.mat.sbg.ac.at/pub/data/wsc95.psThe output sequence is defined by x(n+1) = (a*inv(x(n)) - b) (mod p), where x(0), a, b, and the prime number p are parameters of the generator. The expression inv(k) denotes the multiplicative inverse of k in the field of integer numbers modulo p, with inv(0) := 0.
The template parameter IntType
shall denote a signed
integral type large enough to hold p; a, b, and p are the parameters of the
generators.
Note: The implementation currently uses the Euclidian Algorithm to compute the multiplicative inverse. Therefore, the inversive generators are about 10-20 times slower than the others (see section"performance"). However, the paper talks of only 3x slowdown, so the Euclidian Algorithm is probably not optimal for calculating the multiplicative inverse.
inversive_congruential(IntType y0 = 1)
Effects: Constructs an
inversive_congruential
generator with y0
as the
initial state.
void seed(IntType y0)
Effects: Changes the current state to
y0
.
The specialization hellekalek1995
was suggested in the
above paper.
random::mersenne_twister
#include <boost/random/mersenne_twister.hpp> template<class DataType, int w, int n, int m, int r, DataType a, int u, int s, DataType b, int t, DataType c, int l, IntType val> class random::mersenne_twister { public: typedef DataType result_type; static const bool has_fixed_range = true; static const result_type min_value; static const result_type max_value; mersenne_twister(); explicit mersenne_twister(DataType value); template<class Generator> explicit mersenne_twister(Generator & gen); // compiler-generated copy ctor and assignment operator are fine void seed(); void seed(DataType value); template<class Generator> void seed(Generator & gen); result_type operator()(); bool validation(result_type) const; }; typedef mersenne_twister<uint32_t,351,175,19,0xccab8ee7,11,7,0x31b6ab00,15,0xffe50000,17, /* unknown */ 0> mt11213b; typedef mersenne_twister<uint32_t,624,397,31,0x9908b0df,11,7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;
Instantiations of class template mersenne_twister
model a
pseudo-random number
generator. It uses the algorithm described in
"Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura, ACM Transactions on Modeling and Computer Simulation: Special Issue on Uniform Random Number Generation, Vol. 8, No. 1, January 1998, pp. 3-30.Note: The boost variant has been implemented from scratch and does not derive from or use mt19937.c provided on the above WWW site. However, it was verified that both produce identical output.
mt19937
instead.mt11213b
requires about 1408
bytes and mt19937
requires about 2496 bytes.
mersenne_twister()
Effects: Constructs a mersenne_twister
and
calls seed()
.
explicit mersenne_twister(result_type value)
Effects: Constructs a mersenne_twister
and
calls seed(value)
.
template<class Generator> explicit mersenne_twister(Generator & gen)
Effects: Constructs a mersenne_twister
and
calls seed(gen)
.
Note: When using direct-initialization syntax with an lvalue
(e.g. in the variable definition Gen gen2(gen);
), this
templated constructor will be preferred over the compiler-generated copy
constructor. For variable definitions which should copy the state of
another mersenne_twister
, use e.g. Gen gen2 =
gen;
, which is copy-initialization syntax and guaranteed to invoke
the copy constructor.
void seed()
Effects: Calls
seed(result_type(5489))
.
void seed(result_type value)
Effects: Sets the state x(0) to v mod 2w.
Then, iteratively,
sets x(i) to (i + 1812433253 * (x(i-1) xor (x(i-1) rshift
w-2))) mod 2w for i = 1 .. n-1. x(n) is the first value to be
returned by operator().
template<class Generator> void seed(Generator & gen)
Effects: Sets the state of this
mersenne_twister
to the values returned by n
invocations of gen
.
Complexity: Exactly n
invocations of
gen
.
Note: When invoking seed
with an lvalue, overload
resolution chooses the function template unless the type of the argument
exactly matches result_type
. For other integer types, you
should convert the argument to result_type
explicitly.
The specializations mt11213b
and mt19937
are
from the paper cited above.
random::lagged_fibonacci
#include <boost/random/lagged_fibonacci.hpp> template<class FloatType, unsigned int p, unsigned int q> class lagged_fibonacci { public: typedef FloatType result_type; static const bool has_fixed_range = false; static const unsigned int long_lag = p; static const unsigned int short_lag = q; result_type min() const { return 0.0; } result_type max() const { return 1.0; } lagged_fibonacci(); explicit lagged_fibonacci(uint32_t value); template<class Generator> explicit lagged_fibonacci(Generator & gen); // compiler-generated copy ctor and assignment operator are fine void seed(uint32_t value = 331u); template<class Generator> void seed(Generator & gen); result_type operator()(); bool validation(result_type x) const; }; typedef random::lagged_fibonacci<double, 607, 273> lagged_fibonacci607; typedef random::lagged_fibonacci<double, 1279, 418> lagged_fibonacci1279; typedef random::lagged_fibonacci<double, 2281, 1252> lagged_fibonacci2281; typedef random::lagged_fibonacci<double, 3217, 576> lagged_fibonacci3217; typedef random::lagged_fibonacci<double, 4423, 2098> lagged_fibonacci4423; typedef random::lagged_fibonacci<double, 9689, 5502> lagged_fibonacci9689; typedef random::lagged_fibonacci<double, 19937, 9842> lagged_fibonacci19937; typedef random::lagged_fibonacci<double, 23209, 13470> lagged_fibonacci23209; typedef random::lagged_fibonacci<double, 44497, 21034> lagged_fibonacci44497;
Instantiations of class template lagged_fibonacci
model a
pseudo-random number
generator. It uses a lagged Fibonacci algorithm with two lags p and q,
evaluated in floating-point arithmetic: x(i) = x(i-p) + x(i-q) (mod 1) with
p > q. See
"Uniform random number generators for supercomputers", Richard Brent, Proc. of Fifth Australian Supercomputer Conference, Melbourne, Dec. 1992, pp. 704-706.
Note: The quality of the generator crucially depends on the
choice of the parameters. User code should employ one of the sensibly
parameterized generators such as lagged_fibonacci607
instead.
The generator requires considerable amounts of memory for the storage of
its state array. For example, lagged_fibonacci607
requires
about 4856 bytes and lagged_fibonacci44497
requires about 350
KBytes.
lagged_fibonacci()
Effects: Constructs a lagged_fibonacci
generator and calls seed()
.
explicit lagged_fibonacci(uint32_t value)
Effects: Constructs a lagged_fibonacci
generator and calls seed(value)
.
template<class Generator> explicit lagged_fibonacci(Generator & gen)
Effects: Constructs a lagged_fibonacci
generator and calls seed(gen)
.
void seed()
Effects: Calls seed(331u)
.
void seed(uint32_t value)
Effects: Constructs a minstd_rand0
generator with the constructor parameter value
and calls
seed
with it.
template<class Generator> void seed(Generator & gen)
Effects: Sets the state of this
lagged_fibonacci
to the values returned by p
invocations of uniform_01<gen, FloatType>
.
Complexity: Exactly p
invocations of
gen
.
The specializations lagged_fibonacci607
...
lagged_fibonacci44497
(see above) use well tested lags.
(References will be added later.)
The test program random_speed.cpp measures the execution times of the random.hpp implementation of the above algorithms in a tight loop. The performance has been evaluated on a Pentium Pro 200 MHz with gcc 2.95.2, Linux 2.2.13, glibc 2.1.2.
class | time per invocation [usec] |
---|---|
rand48 | 0.096 |
rand48 run-time configurable | 0.697 |
lrand48 glibc 2.1.2 | 0.844 |
minstd_rand | 0.174 |
ecuyer1988 | 0.445 |
kreutzer1986 | 0.249 |
hellekalek1995 (inversive) | 4.895 |
mt11213b | 0.165 |
mt19937 | 0.165 |
mt19937 original | 0.185 |
lagged_fibonacci607 | 0.111 |
lagged_fibonacci4423 | 0.112 |
lagged_fibonacci19937 | 0.113 |
lagged_fibonacci23209 | 0.122 |
lagged_fibonacci44497 | 0.263 |
The measurement error is estimated at +/- 10 nsec.
Revised 05 December, 2006
Copyright © 2000-2005 Jens Maurer
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)