[rand.eng.mers]

# 29 Numerics library [[numerics]](./#numerics)

## 29.5 Random number generation [[rand]](rand#eng.mers)

### 29.5.4 Random number engine class templates [[rand.eng]](rand.eng#mers)

#### 29.5.4.3 Class template mersenne_twister_engine [rand.eng.mers]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2793)

A mersenne_twister_engine random number
engine[242](#footnote-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.") produces unsigned integer random numbers
in the closed interval [0,2w−1][.](#1.sentence-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[.](#1.sentence-2)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2812)

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[.](#2.sentence-1)

To improve the uniformity of the result,
the bits of the raw shift register are additionally [*tempered*](#def:tempered) (i.e., scrambled) according to a bit-scrambling matrix
defined by values u, d, s, b, t, c, and ℓ[.](#2.sentence-2)

The state transition is performed as follows:

- [(2.1)](#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.1.sentence-1)

- [(2.2)](#2.2)

  With α=aâ‹(Ybitand1),
 set Xi to Xi+m−nxor(Yrshift1)xorα[.](#2.2.sentence-1)

The sequence X is initialized
with the help of an initialization multiplier f[.](#2.sentence-4)

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2838)

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

- [(3.1)](#3.1)

  Let z1=Xixor((Xirshiftu)bitandd)[.](#3.1.sentence-1)

- [(3.2)](#3.2)

  Let z2=z1xor((z1lshiftws)bitandb)[.](#3.2.sentence-1)

- [(3.3)](#3.3)

  Let z3=z2xor((z2lshiftwt)bitandc)[.](#3.3.sentence-1)

- [(3.4)](#3.4)

  Let z4=z3xor(z3rshiftℓ)[.](#3.4.sentence-1)

[🔗](#lib:mersenne_twister_engine_)

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<class Sseq> explicit mersenne_twister_engine(Sseq& q); void seed(result_type value = default_seed); template<class Sseq> 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](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2911)

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[.](#4.sentence-1)

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2929)

The textual representation
of xi consists of the values of Xi−n,…,Xi−1,
in that order[.](#5.sentence-1)

[🔗](#lib:mersenne_twister_engine,constructor)

`explicit mersenne_twister_engine(result_type value);
`

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2941)

*Effects*: Sets X−n to valuemod2w[.](#6.sentence-1)

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

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2954)

*Complexity*: O(n)[.](#7.sentence-1)

[🔗](#lib:mersenne_twister_engine,constructor_)

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

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2965)

*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[.](#8.sentence-1)

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[.](#8.sentence-2)

[242)](#footnote-242)[242)](#footnoteref-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[.](#footnote-242.sentence-1)