cppdraft_translate/cppdraft/rand/eng/mers.md

[rand.eng.mers]

29 Numerics library [numerics]

29.5 Random number generation [rand]

29.5.4 Random number engine class templates [rand.eng]

29.5.4.3 Class template mersenne_twister_engine [rand.eng.mers]

1

#

A mersenne_twister_engine random number engine242 produces unsigned integer random numbers in the closed interval [0,2w−1].

The statexi 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.

2

#

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 Xi−n with the lower r bits of Xi+1−n to obtain an unsigned integer value Y.

• (2.2)

  With α=aâ‹(Ybitand1), set Xi to Xi+m−nxor(Yrshift1)xorα.

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

3

#

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

• (3.1)

  Let z1=Xixor((Xirshiftu)bitandd).

• (3.2)

  Let z2=z1xor((z1lshiftws)bitandb).

• (3.3)

  Let z3=z2xor((z2lshiftwt)bitandc).

• (3.4)

  Let z4=z3xor(z3rshiftℓ).

🔗

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:// typesusing result_type = UIntType; // engine characteristicsstatic 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 explicit mersenne_twister_engine(Sseq& q); void seed(result_type value = default_seed); template void seed(Sseq& q); // equality operatorsfriend bool operator==(const mersenne_twister_engine& x, const mersenne_twister_engine& y); // generating functions result_type operator()(); void discard(unsigned long long z); // inserters and extractorstemplate<class charT, class traits>friend basic_ostream<charT, traits>&operator<<(basic_ostream<charT, traits>& os, // hostedconst 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); };}

4

#

The following relations shall hold: 0 < m, m <= n, 2u < w, r <= w, u <= w, s <= w, t <= w, l <= w, w <= numeric_limits​::​digits, a <= (1u << w) - 1u, b <= (1u << w) - 1u, c <= (1u << w) - 1u, d <= (1u << w) - 1u, and f <= (1u << w) - 1u.

5

#

The textual representation of xi consists of the values of Xi−n,…,Xi−1, in that order.

🔗

explicit mersenne_twister_engine(result_type value);

6

#

Effects: Sets X−n to valuemod2w.

Then, iteratively for i=1−n,…,−1, sets Xi to
[fâ‹(Xi−1xor(Xi−1rshift(w−2)))+imodn]mod2w.

7

#

Complexity: O(n).

🔗

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

8

#

Effects: With k=⌈w/32⌉ and a an array (or equivalent) of length nâ‹k, invokes q.generate(a+0, a+nâ‹k) and then, iteratively for i=−n,…,−1, sets Xi to (∑k−1j=0ak(i+n)+jâ‹232j)mod2w.

Finally, if the most significant w−r bits of X−n are zero, and if each of the other resulting Xi is 0, changes X−n to 2w−1.

242)242)

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.