Random Number Library Generators
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.
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.
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
Synopsis
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
};
Description
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
Member functions
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
Synopsis
#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;
Description
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-146
Let 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.
Members
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-146
It 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
Synopsis
#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()();
};
Description
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.
Constructors
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 .
Seeding
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 .
Synopsis
#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;
Description
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, 774
The 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 .
Members
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.
Synopsis
#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;
};
Description
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 .
Members
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.
Synopsis
#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;
Description
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.ps
The 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.
Members
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.
Synopsis
#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;
Description
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.
The seeding from an integer was changed in April 2005 to address a weakness.
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 mt19937 instead.
The generator requires considerable amounts of memory for the storage of
its state array. For example, mt11213b requires about 1408
bytes and mt19937 requires about 2496 bytes.
Constructors
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.
Seeding
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.
Synopsis
#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;
Description
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.
Constructors
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) .
Seeding
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 .
Specializations
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)
|