[rand.eng.mers]

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 .}_{i + 1 - n to obtain an unsigned integer value Y .}}_{i - n with the lower r bits of {X i + 1 - n to obtain an unsigned integer value Y .}_{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 α .}_{i + m - n x o r (Y r s h i f t 1) x o r α .}}_{i to {X i + m - n x o r (Y r s h i f t 1) x o r α .}_{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

🔗

namespace std { 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

2w−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); / equality operators friend bool operator=(const mersenne_twister_engine& x, const mersenne_twister_engine& y); / generating functions result_type operator()(); void discard(unsigned long z); / inserters and extractors template<class charT, class traits> friend basic_ostream<charT, traits>& operator<(basic_ostream<charT, traits>& os, / hosted const mersenne_twister_engine& x); template<class charT, class traits> friend basic_istream<charT, traits>& operator>(basic_istream<charT, traits>& is, / hosted mersenne_twister_engine& x); }; }

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 .}_{i - 1, in that order .}}_{i - n, \dots, {X i - 1, in that order .}_{i - 1, in that order .}}}_{i consists of the values of {X i - n, \dots, {X i - 1, in that order .}_{i - 1, in that order .}}_{i - n, \dots, {X i - 1, in that order .}_{i - 1, in that order .}}}

🔗

explicit mersenne_twister_engine(result_type value);

Effects: Sets

{X - n to value mod {2 w .}^{w .}}_{- n to value mod {2 w .}^{w .}}

Then, iteratively for

i = 1 - n, \dots, - 1, sets {X i to [f \cdot ({X i - 1 x o r ({X i - 1 r s h i f t (w - 2))}_{i - 1 r s h i f t (w - 2))}}_{i - 1 x o r ({X i - 1 r s h i f t (w - 2))}_{i - 1 r s h i f t (w - 2))}}}_{i to [f \cdot ({X i - 1 x o r ({X i - 1 r s h i f t (w - 2))}_{i - 1 r s h i f t (w - 2))}}_{i - 1 x o r ({X i - 1 r s h i f t (w - 2))}_{i - 1 r s h i f t (w - 2))) + i mod n}}}

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 to ({\sum k - 1 j = 0 {a k (i + n) + j \cdot}_{k (i + n) + j \cdot 2}}^{k - 1 j = 0 {a k (i + n) + j \cdot 2}_{k (i + n) + j \cdot 2^{32 j) mod}}}}_{i to ({\sum k - 1 j = 0 {a k (i + n) + j \cdot 2}_{k (i + n) + j \cdot 2}}^{k - 1 j = 0 {a k (i + n) + j \cdot 2^{32 j) mod}}_{k (i + n) + j \cdot {2 32 j) mod}^{32 j) mod^{.}}}}}

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 to {2 w - 1 .}^{w - 1 .}}_{- n to {2 w - 1 .}^{w - 1 .}}}_{i is 0, changes {X - n to {2 w - 1 .}^{w - 1 .}}_{- n to {2 w - 1 .}^{w - 1 .}}}}_{- n are zero, and if each of the other resulting {X i is 0, changes {X - n to {2 w - 1 .}^{w - 1 .}}_{- n to {2 w - 1 .}^{w - 1 .}}}_{i is 0, changes {X - n to {2 w - 1 .}^{w - 1 .}}_{- n to {2 w - 1 .}^{w - 1 .}}}}

234)234)

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.