29 Numerics library [numerics]

29.6 Random number generation [rand]

29.6.3 Random number engine class templates [rand.eng] Class template mersenne_­twister_­engine [rand.eng.mers]

A mersenne_­twister_­engine random number engine270 produces unsigned integer random numbers in the closed interval [0,2w1]. The state xi 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 u,d,s,b,t,c, and .

The state transition is performed as follows:

  1. a)Concatenate the upper wr bits of Xin with the lower r bits of Xi+1n to obtain an unsigned integer value Y.

  2. b)With α=a(Ybitand1), set Xi to Xi+mnxor(Yrshift1)xorα.

The sequence X is initialized with the help of an initialization multiplier f.

The generation algorithm determines the unsigned integer values z1,z2,z3,z4 as follows, then delivers z4 as its result:

  1. a)Let z1=Xixor((Xirshiftu)bitandd).

  2. b)Let z2=z1xor((z1lshiftws)bitandb).

  3. c)Let z3=z2xor((z2lshiftwt)bitandc).

  4. d)Let z4=z3xor(z3rshift).

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 {
    // 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  2w1; }
    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 xi consists of the values of Xin,,Xi1, in that order.

explicit mersenne_twister_engine(result_type value = default_seed);

Effects: Constructs a mersenne_­twister_­engine object. Sets Xn to valuemod2w. Then, iteratively for i=1n,,1, sets Xi to


Complexity: O(n).

template<class Sseq> explicit mersenne_twister_engine(Sseq& q);

Effects: Constructs a mersenne_­twister_­engine object. With k=w/32 and a an array (or equivalent) of length nk, invokes q.generate(a+0, a+nk) and then, iteratively for i=n,,1, sets Xi to (k1j=0ak(i+n)+j232j)mod2w. Finally, if the most significant wr bits of Xn are zero, and if each of the other resulting Xi is 0, changes Xn to 2w1.

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.