26 Numerics library [numerics]

A mersenne_twister_engine random number engine276 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:

1. (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.2)

   With α = a · (Y   bitand   1), set X_i to X_i+m-n     xor     (Y   rshift   1)     xor     α.

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

The generation algorithm determines the unsigned integer values z₁, z₂, z₃, z₄ as follows, then delivers z₄ as its result:

1. (3.1)

   Let z₁ = X_i   xor   (( X_i   rshift   u )   bitand   d).

2. (3.2)

   Let z₂ = z₁   xor   ( (z₁   lshift_w     s)   bitand   b ).

3. (3.3)

   Let z₃ = z₂   xor   ( (z₂   lshift_w     t)   bitand   c ).

4. (3.4)

   Let z₄ = z₃   xor   ( z₃   rshift   ℓ ).

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
 typedef UIntType result_type;

 // 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
 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_i consists of the values of X_i-n, …, X_i-1, in that order.

explicit mersenne_twister_engine(result_type value = default_seed);