29 Numerics library [numerics]

29.6 Random number generation [rand]

29.6.3 Random number engine class templates [rand.eng]

29.6.3.2 Class template mersenne_­twister_­engine [rand.eng.mers]

A mersenne_­twister_­engine random number engine271 produces unsigned integer random numbers in the closed interval .
The state x of a mersenne_­twister_­engine object x is of size n and consists of a sequence X of n values of the type delivered by x; all subscripts applied to X are to be taken modulo n.
The transition algorithm employs a twisted generalized feedback shift register defined by shift values n and m, a twist value r, and a conditional xor-mask a.
To improve the uniformity of the result, the bits of the raw shift register are additionally tempered (i.e., scrambled) according to a bit-scrambling matrix defined by values and .
The state transition is performed as follows:
  1. a)
    Concatenate the upper bits of with the lower r bits of to obtain an unsigned integer value Y.
  2. b)
    With , set to .
The sequence X is initialized with the help of an initialization multiplier f.
The generation algorithm determines the unsigned integer values as follows, then delivers as its result:
  1. a)
    Let .
  2. b)
    Let .
  3. c)
    Let .
  4. d)
    Let .
template<class UIntType, size_t w, size_t n, size_t m, size_t r,
         UIntType a, size_t u, UIntType d, size_t s,
         UIntType b, size_t t,
         UIntType c, size_t l, UIntType f>
  class mersenne_twister_engine {
  public:
    // types
    using result_type = UIntType;

    // engine characteristics
    static constexpr size_t word_size = w;
    static constexpr size_t state_size = n;
    static constexpr size_t shift_size = m;
    static constexpr size_t mask_bits = r;
    static constexpr UIntType xor_mask = a;
    static constexpr size_t tempering_u = u;
    static constexpr UIntType tempering_d = d;
    static constexpr size_t tempering_s = s;
    static constexpr UIntType tempering_b = b;
    static constexpr size_t tempering_t = t;
    static constexpr UIntType tempering_c = c;
    static constexpr size_t tempering_l = l;
    static constexpr UIntType initialization_multiplier = f;
    static constexpr result_type min() { return 0; }
    static constexpr result_type max() { return  ; }
    static constexpr result_type default_seed = 5489u;

    // constructors and seeding functions
    explicit mersenne_twister_engine(result_type value = default_seed);
    template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
    void seed(result_type value = default_seed);
    template<class Sseq> void seed(Sseq& q);

    // generating functions
    result_type operator()();
    void discard(unsigned long long z);
  };
The following relations shall hold: 0 < m, m <= n, 2u < w, r <= w, u <= w, s <= w, t <= w, l <= w, w <= numeric_­limits<UIntType>​::​digits, a <= (1u<<w) - 1u, b <= (1u<<w) - 1u, c <= (1u<<w) - 1u, d <= (1u<<w) - 1u, and f <= (1u<<w) - 1u.
The textual representation of x consists of the values of , in that order.
explicit mersenne_twister_engine(result_type value = default_seed);
Effects: Constructs a mersenne_­twister_­engine object.
Sets to .
Then, iteratively for , sets to

Complexity: .
template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
Effects: Constructs a mersenne_­twister_­engine object.
With and a an array (or equivalent) of length , invokes q.generate(, ) and then, iteratively for , sets to .
Finally, if the most significant bits of are zero, and if each of the other resulting is 0, changes to .
The name of this engine refers, in part, to a property of its period: For properly-selected values of the parameters, the period is closely related to a large Mersenne prime number.