Random Number Library Generators

• Introduction
• Synopsis
• Class template random::const_mod
• Class template random::linear_congruential
• Class rand48
• Class template random::additive_combined
• Class template random::shuffle_output
• Class template random::inversive_congruential
• Class template random::mersenne_twister
• Class template random::lagged_fibonacci
• Performance

Introduction

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.

Synopsis of the generators available from header <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

Class template random::const_mod

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

Class template random::linear_congruential

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

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.

Specializations

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

"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

Class rand48

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.

Class template random::additive_combine

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 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.

Specialization

The specialization ecuyer1988 was suggested in the above paper.

Class template random::shuffle_output

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.

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.

Specializations

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.

Class template random::inversive_congruential

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 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.

Specialization

The specialization hellekalek1995 was suggested in the above paper.

Class template random::mersenne_twister

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.

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 2^w. Then, iteratively,
sets x(i) to (i + 1812433253 * (x(i-1) xor (x(i-1) rshift w-2))) mod 2^w 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.

Specializations

The specializations mt11213b and mt19937 are from the paper cited above.

Class template random::lagged_fibonacci

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.)

Performance

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.

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)