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

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

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 usually has acceptable quality.

Note: These random number generators are not indended 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 in 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 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 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

    template<class IntType, IntType a, IntType c, IntType m>
    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`.

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

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

## Class `rand48`

### Synopsis

    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

    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.

### Specialization

The specialization `ecuyer1988` was suggested in the above paper.

## Class template `random::shuffle_output`

### Synopsis

    template<class UniformRandomNumberGenerator, int k,
      class IntType = typename UniformRandomNumberGenerator::result_type,
      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. As an implementation detail, the template parameter `IntType` shall denote an integer-like type which is large enough to hold integer numbers of value k * `base_type::max()`. 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

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

### Specialization

The specialization `hellekalek1995` was suggested in the above paper.

## Class template `random::mersenne_twister`

### Synopsis

    template<class DataType, 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. http://www.math.keio.ac.jp/matumoto/emt.html

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 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(DataType 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 invoke the copy constructor.

### Seeding

    void seed()

Effects: Calls `seed(4357)`.

    void seed(DataType value)

Effects: Constructs a `linear_congruential<uint32_t, 69069, 0, 0, 0>` generator with the constructor parameter `value` and calls `seed` with it.

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

### Specializations

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

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

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

The measurement error is estimated at +/- 10 nsec.

Jens Maurer, 2000-10-01