Boost C++ Libraries

Random numbers are required in a number of different problem domains, such as

The Boost Random Number Generator Library provides a framework for random number generators with well-defined properties so that the generators can be used in the demanding numerics and security domains. For a general introduction to random numbers in numerics, see

Depending on the requirements of the problem domain, different variations of random number generators are appropriate:

All variations have some properties in common, the concepts (in the STL sense) is called UniformRandomNumberGenerator. This concept will be defined in a subsequent section.

The goals for this library are the following:

A uniform random number generator provides a sequence of random numbers uniformly distributed on a given range. The range can be compile-time fixed or available (only) after run-time construction of the object.

The tight lower bound of some (finite) set S is the (unique) member l in S, so that for all v in S, l <= v holds. Likewise, the tight upper bound of some (finite) set S is the (unique) member u in S, so that for all v in S, v <= u holds.

In the following table, X denotes a number generator class returning objects of type T, and v is a const value of X.

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

Note

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

	Note
	The UniformRandomNumberGenerator concept does not require operator()(long) and thus it does not fulfill the RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]) requirements. Use the random_number_generator adapter for that. Rationale: operator()(long) is not provided, because mapping the output of some generator with integer range to a different integer range is not trivial.

A non-deterministic uniform random number generator is a UniformRandomNumberGenerator that is based on some stochastic process. Thus, it provides a sequence of truly-random numbers. Examples for such processes are nuclear decay, noise of a Zehner diode, tunneling of quantum particles, rolling a die, drawing from an urn, and tossing a coin. Depending on the environment, inter-arrival times of network packets or keyboard events may be close approximations of stochastic processes.

The class random_device is a model for a non-deterministic random number generator.

Note

This type of random-number generator is useful for security applications, where it is important to prevent an outside attacker from guessing the numbers and thus obtaining your encryption or authentication key. Thus, models of this concept should be cautious not to leak any information, to the extent possible by the environment. For example, it might be advisable to explicitly clear any temporary storage as soon as it is no longer needed.

A pseudo-random number generator is a UniformRandomNumberGenerator which provides a deterministic sequence of pseudo-random numbers, based on some algorithm and internal state. Linear congruential and inversive congruential generators are examples of such pseudo-random number generators. Often, these generators are very sensitive to their parameters. In order to prevent wrong implementations from being used, an external testsuite should check that the generated sequence and the validation value provided do indeed match.

Donald E. Knuth gives an extensive overview on pseudo-random number generation in his book "The Art of Computer Programming, Vol. 2, 3rd edition, Addison-Wesley, 1997". The descriptions for the specific generators contain additional references.

	Note
	Because the state of a pseudo-random number generator is necessarily finite, the sequence of numbers returned by the generator will loop eventually.

In addition to the UniformRandomNumberGenerator requirements, a pseudo-random number generator has some additional requirements. In the following table, X denotes a pseudo-random number generator class returning objects of type T, x is a value of T, u is a value of X, and v is a const value of X.

	Note
	The seed member function is similar to the assign member function in STL containers. However, the naming did not seem appropriate.

Classes which model a pseudo-random number generator shall also model EqualityComparable, i.e. implement operator==. Two pseudo-random number generators are defined to be equivalent if they both return an identical sequence of numbers starting from a given state.

Classes which model a pseudo-random number generator should also model the Streamable concept, i.e. implement operator<< and operator>>. If so, operator<< writes all current state of the pseudo-random number generator to the given ostream so that operator>> can restore the state at a later time. The state shall be written in a platform-independent manner, but it is assumed that the locales used for writing and reading be the same. The pseudo-random number generator with the restored state and the original at the just-written state shall be equivalent.

Classes which model a pseudo-random number generator should also model the CopyConstructible and Assignable concepts. However, note that the sequences of the original and the copy are strongly correlated (in fact, they are identical), which may make them unsuitable for some problem domains. Thus, copying pseudo-random number generators is discouraged; they should always be passed by (non-const) reference.

The classes rand48, minstd_rand, and mt19937 are models for a pseudo-random number generator.

Note

This type of random-number generator is useful for numerics, games and testing. The non-zero arguments constructor(s) and the seed() member function(s) allow for a user-provided state to be installed in the generator. This is useful for debugging Monte-Carlo algorithms and analyzing particular test scenarios. The Streamable concept allows to save/restore the state of the generator, for example to re-run a test suite at a later time.

A random distribution produces random numbers distributed according to some distribution, given uniformly distributed random values as input. In the following table, X denotes a random distribution class returning objects of type T, u is a value of X, x is a (possibly const) value of X, and e is an lvalue of an arbitrary type that meets the requirements of a UniformRandomNumberGenerator, returning values of type U.

Additional requirements: The sequence of numbers produced by repeated invocations of x(e) does not change whether or not os << x is invoked between any of the invocations x(e). If a textual representation is written using os << x and that representation is restored into the same or a different object y of the same type using is >> y, repeated invocations of y(e) produce the same sequence of random numbers as would repeated invocations of x(e).

namespace boost {
  namespace random {
    template<typename MLCG1, typename MLCG2> class additive_combine_engine;
    typedef additive_combine_engine< linear_congruential_engine< uint32_t, 40014, 0, 2147483563 >, linear_congruential_engine< uint32_t, 40692, 0, 2147483399 >> ecuyer1988;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class bernoulli_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename IntType = int, typename RealType = double> 
      class binomial_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class cauchy_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class chi_squared_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename UniformRandomNumberGenerator, std::size_t p, 
             std::size_t r> 
      class discard_block_engine;
  }
}

namespace boost {
  namespace random {
    template<typename IntType = int, typename WeightType = double> 
      class discrete_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class exponential_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class extreme_value_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class fisher_f_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class gamma_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename IntType = int, typename RealType = double> 
      class geometric_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename Engine, std::size_t w, typename UIntType> 
      class independent_bits_engine;
  }
}

namespace boost {
  namespace random {
    template<typename IntType, IntType a, IntType b, IntType p> 
      class inversive_congruential_engine;
    typedef inversive_congruential_engine< uint32_t, 9102, 2147483647-36884165, 2147483647 > hellekalek1995;
  }
}

namespace boost {
  namespace random {
    template<typename UIntType, int w, unsigned int p, unsigned int q> 
      class lagged_fibonacci_engine;
    template<typename RealType, int w, unsigned int p, unsigned int q> 
      class lagged_fibonacci_01_engine;
    typedef lagged_fibonacci_01_engine< double, 48, 607, 273 > lagged_fibonacci607;
    typedef lagged_fibonacci_01_engine< double, 48, 1279, 418 > lagged_fibonacci1279;
    typedef lagged_fibonacci_01_engine< double, 48, 2281, 1252 > lagged_fibonacci2281;
    typedef lagged_fibonacci_01_engine< double, 48, 3217, 576 > lagged_fibonacci3217;
    typedef lagged_fibonacci_01_engine< double, 48, 4423, 2098 > lagged_fibonacci4423;
    typedef lagged_fibonacci_01_engine< double, 48, 9689, 5502 > lagged_fibonacci9689;
    typedef lagged_fibonacci_01_engine< double, 48, 19937, 9842 > lagged_fibonacci19937;
    typedef lagged_fibonacci_01_engine< double, 48, 23209, 13470 > lagged_fibonacci23209;
    typedef lagged_fibonacci_01_engine< double, 48, 44497, 21034 > lagged_fibonacci44497;
  }
}

namespace boost {
  namespace random {
    template<typename IntType, IntType a, IntType c, IntType m> 
      class linear_congruential_engine;
    class rand48;
    typedef linear_congruential_engine< uint32_t, 16807, 0, 2147483647 > minstd_rand0;
    typedef linear_congruential_engine< uint32_t, 48271, 0, 2147483647 > minstd_rand;
  }
}

namespace boost {
  namespace random {
    template<typename UIntType, int w, int k, int q, int s> 
      class linear_feedback_shift_engine;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class lognormal_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename UIntType, std::size_t w, std::size_t n, std::size_t m, 
             std::size_t r, UIntType a, std::size_t u, UIntType d, 
             std::size_t s, UIntType b, std::size_t t, UIntType c, 
             std::size_t l, UIntType f> 
      class mersenne_twister_engine;
    typedef mersenne_twister_engine< uint32_t, 32, 351, 175, 19, 0xccab8ee7, 11, 0xffffffff, 7, 0x31b6ab00, 15, 0xffe50000, 17, 1812433253 > mt11213b;
    typedef mersenne_twister_engine< uint32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7, 0x9d2c5680, 15, 0xefc60000, 18, 1812433253 > mt19937;
    typedef mersenne_twister_engine< uint64_t, 64, 312, 156, 31, 0xb5026f5aa96619e9ull, 29, 0x5555555555555555ull, 17, 0x71d67fffeda60000ull, 37, 0xfff7eee000000000ull, 43, 6364136223846793005ull > mt19937_64;
  }
}

namespace boost {
  namespace random {
    template<typename IntType = int, typename RealType = double> 
      class negative_binomial_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class normal_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double, typename WeightType = double> 
      class piecewise_constant_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class piecewise_linear_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename IntType = int, typename RealType = double> 
      class poisson_distribution;
  }
}

namespace boost {
  namespace random {
    class random_device;
  }
}

namespace boost {
  namespace random {
    template<typename URNG, typename IntType = long> 
      class random_number_generator;
  }
}

namespace boost {
  namespace random {
    typedef subtract_with_carry_engine< uint32_t, 24, 10, 24 > ranlux_base;
    typedef subtract_with_carry_01_engine< float, 24, 10, 24 > ranlux_base_01;
    typedef subtract_with_carry_01_engine< double, 48, 10, 24 > ranlux64_base_01;
    typedef discard_block_engine< ranlux_base, 223, 24 > ranlux3;
    typedef discard_block_engine< ranlux_base, 389, 24 > ranlux4;
    typedef discard_block_engine< ranlux_base_01, 223, 24 > ranlux3_01;
    typedef discard_block_engine< ranlux_base_01, 389, 24 > ranlux4_01;
    typedef discard_block_engine< ranlux64_base_01, 223, 24 > ranlux64_3_01;
    typedef discard_block_engine< ranlux64_base_01, 389, 24 > ranlux64_4_01;
    typedef subtract_with_carry_engine< uint64_t, 48, 10, 24 > ranlux64_base;
    typedef discard_block_engine< ranlux64_base, 223, 24 > ranlux64_3;
    typedef discard_block_engine< ranlux64_base, 389, 24 > ranlux64_4;
    typedef subtract_with_carry_engine< uint32_t, 24, 10, 24 > ranlux24_base;
    typedef subtract_with_carry_engine< uint64_t, 48, 5, 12 > ranlux48_base;
    typedef discard_block_engine< ranlux24_base, 223, 23 > ranlux24;
    typedef discard_block_engine< ranlux48_base, 389, 11 > ranlux48;
  }
}

namespace boost {
  namespace random {
    class seed_seq;
  }
}

namespace boost {
  namespace random {
    template<typename UniformRandomNumberGenerator, std::size_t k> 
      class shuffle_order_engine;
    typedef shuffle_order_engine< linear_congruential_engine< uint32_t, 1366, 150889, 714025 >, 97 > kreutzer1986;
    typedef shuffle_order_engine< minstd_rand0, 256 > knuth_b;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class student_t_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename IntType, std::size_t w, std::size_t s, std::size_t r> 
      class subtract_with_carry_engine;
    template<typename RealType, std::size_t w, std::size_t s, std::size_t r> 
      class subtract_with_carry_01_engine;
  }
}

namespace boost {
  namespace random {
    typedef xor_combine_engine< xor_combine_engine< linear_feedback_shift_engine< uint32_t, 32, 31, 13, 12 >, 0, linear_feedback_shift_engine< uint32_t, 32, 29, 2, 4 >, 0 >, 0, linear_feedback_shift_engine< uint32_t, 32, 28, 3, 17 >, 0 > taus88;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class triangle_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class uniform_01;
  }
}

namespace boost {
  namespace random {
    template<typename IntType = int> class uniform_int_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double, 
             typename Cont = std::vector<RealType> > 
      class uniform_on_sphere;
  }
}

namespace boost {
  namespace random {
    template<typename RealType = double> class uniform_real_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename IntType = int> class uniform_smallint;
  }
}

namespace boost {
  template<typename Engine, typename Distribution> class variate_generator;
}

namespace boost {
  namespace random {
    template<typename RealType = double> class weibull_distribution;
  }
}

namespace boost {
  namespace random {
    template<typename URNG1, int s1, typename URNG2, int s2> 
      class xor_combine_engine;
  }
}