26 Numerics library [numerics]

26.6 Random number generation [rand]

26.6.3 Random number engine class templates [rand.eng]

26.6.3.2 Class template mersenne_twister_engine [rand.eng.mers]

A mersenne_twister_engine random number engine243 produces unsigned integer random numbers in the closed interval

[0, 2^{w} - 1]

The state x

_{i}

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:

(2.1)
Concatenate the upper $w - r$ bits of $X_{i - n}$ with the lower r bits of $X_{i + 1 - n}$ to obtain an unsigned integer value Y.
(2.2)
With $α = a \cdot (Y b i t a n d 1)$ , set $X_{i}$ to $X_{i + m - n} x o r (Y r s h i f t 1) x o r α$ .

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

The generation algorithm determines the unsigned integer values

z_{1}, z_{2}, z_{3}, z_{4}

as follows, then delivers

z_{4}

as its result:

(3.1)
Let $z_{1} = X_{i} x o r ((X_{i} r s h i f t u) b i t a n d d)$ .
(3.2)
Let $z_{2} = z_{1} x o r ((z_{1} {l s h i f t}_{w} s) b i t a n d b)$ .
(3.3)
Let $z_{3} = z_{2} x o r ((z_{2} {l s h i f t}_{w} t) b i t a n d c)$ .
(3.4)
Let $z_{4} = z_{3} x o r (z_{3} r s h i f t ℓ)$ .

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   $2^{w} - 1$ ; }
    static constexpr result_type default_seed = 5489u;

    // constructors and seeding functions
    mersenne_twister_engine() : mersenne_twister_engine(default_seed) {}
    explicit mersenne_twister_engine(result_type value);
    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

_{i}

consists of the values of

X_{i - n}, \dots, X_{i - 1}

, in that order.

🔗

explicit mersenne_twister_engine(result_type value);

Effects: Sets

X_{- n}

value mod 2^{w}

Then, iteratively for

i = 1 - n, \dots, - 1

, sets

X_{i}

[f \cdot (X_{i - 1} x o r (X_{i - 1} r s h i f t (w - 2))) + i mod n] mod 2^{w} .

Complexity:

O (n)

🔗

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

Effects: With

k = ⌈ w / 32 ⌉

and a an array (or equivalent) of length

n \cdot k

, invokes q.generate(

a + 0

a + n \cdot k

) and then, iteratively for

i = - n, \dots, - 1

, sets

X_{i}

(\sum_{j = 0}^{k - 1} a_{k (i + n) + j} \cdot 2^{32 j}) mod 2^{w}

Finally, if the most significant

w - r

bits of

X_{- n}

are zero, and if each of the other resulting

X_{i}

is 0, changes

X_{- n}

2^{w - 1}

243)

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.

⮥

26 Numerics library [numerics]

26.6 Random number generation [rand]

26.6.3 Random number engine class templates [rand.eng]

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

26.6.3.2 Class template mersenne_twister_engine [rand.eng.mers]