马特赛特旋转演算法（MernneTwister）
Some of Mernne Twister
认识⼀下马特赛特旋转演算法
Mernne Twister算法是⼀个伪随机数发⽣器(PRNG)，其主要作⽤是⽣成伪随机数，它是⽬前为⽌应⽤最⼴泛的伪随机⽣成器，此算法的名字起于周期长度通常取Mernne质数这样⼀个事实。马特赛特旋转演算法是Makoto Matsumoto （松本）和Takuji Nishimura （西村）于1997年开发的，基于有限⼆进制字段上的矩阵线性再⽣。可以快速产⽣⾼质量的伪随机数，修正了古⽼随机数产⽣算法的很多缺陷。最普遍使⽤的此算法版本是基于梅森质数219937−1，它的标准继承MT19937使⽤32位字长；此外还存在另⼀种使⽤64位字长的继承算法MT19937-64，它产⽣完全不同的序列。
The Mernne Twister is a pudorandom number generator (PRNG). It is by far the most widely ud general-purpo PRNG.[1] Its name derives from th e fact that its period length is chon to be a Mernne prime.
针锋相对的近义词The Mernne Twister was developed in 1997 by Makoto Matsumoto (ja) (松本眞) and Takuji Nishimura (西村拓⼠).[2] It was designed specifically to recti fy most of the flaws found in older PRNGs. It was the first PRNG to provide fast generation of high-quality pudorandom integers.
The most commonly ud version of the Mernne Twister algorithm is bad on the Mernne prime 219937−1. The standard implementation of that, MT 19937, us a 32-bit word length. There is another implementation that us a 64-bit word length, MT19937-64; it generates a different quence.
Adoption in software systems
软件系统中的使⽤
The Mernne Twister is the default PRNG for the following software systems:
在以下系统中马特赛特演算法是默认的伪随机数发⽣器：
三月份星座
Microsoft Visual C++,[3] Microsoft Excel,[4] GAUSS,[5] GLib,[6] GNU Multiple Precision Arithmetic Library,[7] GNU Octave,[8] GNU Scientific Library,[9] g retl,[10] IDL,[11] Julia,[12] CMU Common Lisp,[13] Embeddable Common Lisp,[14] Steel Bank Common Lisp,[15] Maple,[16] MATLAB,[17] Free Pascal,[18 ] PHP,[19] Python,[20][21] R,[22] Ruby,[23] SageMath,[24] Scilab,[25] Stata.[26] It is also available in Apache Commons,[27] in standard C++ (since C++11 ),[28][29] and in Mathematica.[30] Add-on implementations are provided in many program libraries, including the Boost C++ Libraries,[31] the CUDA Librar y,[32] and the NAG Numerical Library.[33]
马特赛特旋转演算法是SPSS中伪随机⽣成器之⼀：另外⼀种⽣成器只对旧的程序保持兼容性，相对的马特赛特算法被认为更加可⾏。马特赛特算法也与SAS中的⼀个伪随机⽣成器类似，但是另外⼀个被认为很⽼旧⽽且已经不被赞成使⽤。
The Mernne Twister is one of two PRNGs in SPSS: the other generator is kept only for compatibility with older programs, and the Mernne Twister is st ated to be "more reliable".[34] The Mernne Twister is similarly one of the PRNGs in SAS: the other generators are older and deprecated.[35]
Advantages
优点
The commonly ud version of Mernne Twister, MT19937, which produces a quence of 32-bit integers, has the following desirable properties:
使⽤⼴泛的马特赛特算法MT19937会产⽣⼀个32位整数序列，它拥有以下令⼈满意的特性：
It has a very long period of 219937 − 1. While a long period is not a guarantee of quality in a random number generator, short periods (such as the 232 co mmon in many older software packages) can b
馒头片e problematic.[36]
马特赛特算法拥有⾮常长的219937 − 1周期，尽管龙周期并不是随机数字⽣成的保证，但是短周期(⽐如在许多旧的软件包中使⽤的通⽤232算法)问题更多。
It is k-distributed to 32-bit accuracy for every 1 ≤ k ≤ 623 (请看下⾯的定义).
对于1 ≤ k ≤ 623它是很精确的32位K分布。
It pass numerous tests for statistical randomness, including the Diehard tests.蝉花的功效与作用
它为统计随机性传递很多的测试，包括极端顽固测试
Disadvantages
缺点
The large state space comes with a performance cost: the 2.5 KiB state buffer will place a load on the memory caches. In 2011, Saito & Matsumoto propos ed a version of the Mernne Twister to address this issue. The tiny version, TinyMT, us just 127 bits of state space.[37]
By today's standards, the Mernne Twister is somewhat slow, [38] unless the SFMT implementation is ud (e ction below).
It pass most, but not all, of the stringent TestU01 randomness tests.[39] Becau it is bad on simple linear (xor) operations, it fails tests bad on linea r complexity after relatively few bits of output, despite its extremely large state.[citation needed] Passing the output through a simple hash function can rem edy this weakness.
Multiple Mernne Twister instances that differ only in ed value (but not other parameters) are not generally appropriate for Monte-Carlo simulations that require independent random number generators, though there exists a method for choosing multiple ts of parameter values.[40][41]
It can take a long time to start generating output that pass randomness tests, if the initial state is highly non-random—particularly if the initial state has m any zeros. A conquence of this is that two instances of the generator, started with initial states that are almost the same, will usually output nearly the sa me quence for many iterations, before eventually diverging. The 2002 update to the MT algorithm has improved initialization, so that beginning with such a state is very unlikely.[42]
k-distribution
K分布
A pudorandom quence xi of w-bit integers of period P is said to be k-distributed to v-bit accuracy if the following holds.
Let truncv(x) denote the number formed by the leading v bits of x, and consider P of the kv-bit vectors
( trunc v ( x i ) , trunc v ( x i + 1 ) , . . . , trunc v ( x i + k − 1 ) ) ( 0 ≤ i < P ) {\displaystyle ({\text{trunc}}_{v}(x_{i}),\,{\text{trunc}}_{v}(x_{i+1}),\,...,\,{\text{trun c}}_{v}(x_{i+k-1}))\quad (0\leq i<P)} ({\text{trunc}}_{v}(x_{i}),\,{\text{trunc}}_{v}(x_{i+1}),\,...,\,{\text{trunc}}_{v}(x_{i+k-1}))\quad (0\leq i<P).
关于梦想的图片Then each of the 2kv possible combinations of bits occurs the same number of times in a period, except for the all-zero combination that occurs once less often.
Alternatives
替代选择
The algorithm in its native form is not cryptographically cure. The reason is that obrving a suffici
ent number of iterations (624 in the ca of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations.
A pair of cryptographic stream ciphers bad on output from the Mernne Twister has been propod by Matsumoto, Nishimura, and co-authors. The aut hors claim speeds 1.5 to 2 times faster than Advanced Encryption Standard in counter mode.[43]
An alternative generator, WELL ("Well Equidistributed Long-period Linear"), offers quicker recovery, and equal randomness, and nearly equal speed.[44] Marsaglia's xorshift generators and variants are the fastest in this class.[45]
Algorithmic detail
算法细节
Visualisation of generation of pudo-random 32-bit integers using a Mernne Twister. The ‘Extract number’ ction shows an example where integer 0 has already been output and the index is at integer 1. ‘Generate numbers’ is run when all integers have been output.
For a w-bit word length, the Mernne Twister generates integers in the range [0, 2w−1].
The Mernne Twister algorithm is bad on a matrix linear recurrence over a finite binary field F2. The algorithm is a twisted generalid feedback shift re gister[46] (twisted GFSR, or TGFSR) of rational normal form (TGFSR(R)), with state bit reflection and tempering. The basic idea is to define a ries x i {\di splaystyle x_{i}} x_{i} through a simple recurrence relation, and then output numbers of the form x i T {\displaystyle x_{i}T} x_{i}T, where T {\displaystyle T} T is an invertible F2 matrix called a tempering matrix.
The general algorithm is characterized by the following quantities (some of the explanations make n only after reading the rest of the algorithm):
w: word size (in number of bits)
n: degree of recurrence
m: middle word, an offt ud in the recurrence relation defining the ries x, 1 ≤ m < n
r: paration point of one word, or the number of bits of the lower bitmask, 0 ≤ r ≤ w - 1
a: coefficients of the rational normal form twist matrix
b, c: TGFSR(R) tempering bitmasks
s, t: TGFSR(R) tempering bit shifts
u, d, l: additional Mernne Twister tempering bit shifts/masks
with the restriction that 2nw − r − 1 is a Mernne prime. This choice simplifies the primitivity test and k-distribution test that are needed in the parameter s earch.
The ries x is defined as a ries of w-bit quantities with the recurrence relation:
x k + n := x k + m ⊕ ( ( x k u ∣∣ x k + 1 l ) A ) k = 0 , 1 , … {\displaystyle x_{k+n}:=x_{k+m}\oplus \left(({x_{k}}^{u}\mid \mid {x_{k+1}}^{l})A\right)\qquad \qqua d k=0,1,\ldots } {\displaystyle x_{k+n}:=x_{k+m}\oplus \left(({x_{k}}^{u}\mid \mid {x_{k+1}}^{l})A\right)\qquad \qquad k=0,1,\ldots }
where ∣∣ {\displaystyle \mid \mid } {\displaystyle \mid \mid } denotes concatenation of bit vectors (with upper bits on the left), ⊕ {\displaystyle \oplus } \oplus the bitwi exclusive or (XOR), x k u {\displaystyle {x_{k}}^{u}} {x_{k}}^{u} means the upper w − r {\displaystyle w-r} w-r bits of x k {\displaystyle x_{k}} x_{k} , and x k + 1 l {\displaystyle x_{k+1}^{l}} x_{k+1}^{l} means the lower r {\displaystyle r} r bits of x k + 1 {\displaystyle x_{k+1}} x_{k+1}. The twist transformati on A is defined in rational normal form as:
A = ( 0 I w − 1 a w − 1 ( a w − 2 , … , a 0 ) ) {\displaystyle A={\begin{pmatrix}0&I_{w-1}\\a_{w-1}&(a_{w-2},\ldots ,a_{0})\end{pmatrix}}} A={\begin{pmatrix}0 &I_{w-1}\\a_{w-1}&(a_{w-2},\ldots ,a_{0})\end{pmatrix}}
with In − 1 as the (n − 1) × (n − 1) identity matrix. The rational normal form has the benefit that multiplication by A can be efficiently expresd as: (reme mber that here matrix multiplication is being done in F2, and therefore bitwi XOR takes the place of addition)
x A = { x ≫ 1 x 0 = 0 ( x ≫ 1 ) ⊕ a x 0 = 1 {\displaystyle {\boldsymbol {x}}A={\begin{cas}{\boldsymbol {x}}\gg 1&x_{0}=0\\({\boldsymbol {x}}\gg 1)\oplus {\
boldsymbol {a}}&x_{0}=1\end{cas}}} {\boldsymbol {x}}A={\begin{cas}{\boldsymbol {x}}\gg 1&x_{0}=0\\({\boldsymbol {x}}\gg 1)\oplus {\boldsymbol {a}}& x_{0}=1\end{cas}}
where x0 is the lowest order bit of x.
As like TGFSR(R), the Mernne Twister is cascaded with a tempering transform to compensate for the reduced dimensionality of equidistribution (becaus e of the choice of A being in the rational normal form). Note that this is equivalent to using the matrix A where A = T−1AT for T an invertible matrix, and ther efore the analysis of characteristic polynomial mentioned below still holds.
As with A, we choo a tempering transform to be easily computable, and so do not actually construct T itlf. The tempering is defined in the ca of Mers enne Twister as
y := x ⊕ ((x >> u) & d)
y := y ⊕ ((y << s) & b)
y := y ⊕ ((y << t) & c)
z := y ⊕ (y >> l)
where x is the next value from the ries, y a temporary intermediate value, z the value returned from the algorithm, with <<, >> as the bitwi left and right shifts, and & as the bitwi and. The first and last transforms are added in order to improve lower-bit equidistribution. From the property of TGFSR, s + t ≥ ⌊ w / 2 ⌋ − 1 {\displaystyle s+t\geq \lfloor w/2\rfloor -1} s+t\geq \lfloor w/2\rfloor -1 is required to reach the upper bound of equidistribution for the upper bits.
The coefficients for MT19937 are:
(w, n, m, r) = (32, 624, 397, 31)
a = 9908B0DF16
(u, d) = (11, FFFFFFFF16)
(s, b) = (7, 9D2C568016)
(t, c) = (15, EFC6000016)
l = 18
Note that 32-bit implementations of the Mernne Twister generally have d = FFFFFFFF16. As a result, the d is occasionally omitted from the algorithm description, since the bitwi and with d in that ca has no effect.
The coefficients for MT19937-64 are:[47]
(w, n, m, r) = (64, 312, 156, 31)
a = B5026F5AA96619E916
(u, d) = (29, 555555555555555516)
(s, b) = (17, 71D67FFFEDA6000016)
(t, c) = (37, FFF7EEE00000000016)
l = 43
Initialization
初始化
As should be apparent from the above description, the state needed for a Mernne Twister implementation is an array of n values of w bits each. To initial ize the array, a w-bit ed value is ud to supply x0 through xn − 1 by tting x0 to the ed value and thereafter tting
孩子教育问题xi = f × (xi-1 ⊕ (xi-1 >> (w-2))) + i
for i from 1 to n-1. The first value the algorithm then generates is bad on xn, not bad on x0. The constant f forms another parameter to the generator, though not part of the algorithm proper. The value for f for MT19937 is 1812433253 and for MT19937-64 is 6364136223846793005.[48]
Comparison with classical GFSR
和经典GFSR的对⽐
In order to achieve the 2nw − r − 1 theoretical upper limit of the period in a TGFSR, φB(t) must be a primitive polynomial, φB(t) being the characteristic poly nomial of
B = ( 0 I w ⋯ 0 0 ⋮ I w ⋮⋱⋮⋮⋮ 0 0 ⋯ I w 0 0 0 ⋯ 0 I w − r S 0 ⋯ 0 0 ) ← m -th row {\displaystyle B={\begin{pmatrix}0&I_{w}&\cdots &0&0\\\vdots && &&\\I_{w}&\vdots &\ddots &\vdots &\vdots \\\vdots &&&&\\0&0&\cdots &I_{w}&0\\0&0&\cdots &0&I_{w-r}\\S&0&\cdots &0&0\end{pmatrix}}{\begin{matrix}\\\\\lef tarrow m{\hbox{-th row}}\\\\\\\\\end{matrix}}} B={\begin{pmatrix}0&I_{w}&\cdots &0&0\\\vdots &&&&\\I_{w}&\vdots &\ddots &\vdots &\vdots \\\vdots &&&&\\0&0 &\cdots &I_{w}&0\\0&0&\cdots &0&I_{w-r}\\S&0&\cdots &0&0\end{pmatrix}}{\begin{matrix}\\\\\leftarrow m{\hbox{-th row}}\\\\\\\\\end{matrix}}
S = ( 0 I r I w − r 0 ) A {\displaystyle S={\begin{pmatrix}0&I_{r}\\I_{w-r}&0\end{pmatrix}}A} S={\begin{pmatrix}0&I_{r}\\I_{w-r}&0\end{pmatrix}}A水兵舞入门动作
颈椎米字操
The twist transformation improves the classical GFSR with the following key properties:
The period reaches the theoretical upper limit 2nw − r − 1 (except if initialized with 0)
Equidistribution in n dimensions (e.g. linear congruential generators can at best manage reasonable distribution in five dimensions)
Pudocode
伪代码
The following piece of pudocode implements the general Mernne Twister algorithm. The constants w, n, m, r, a, u, d, s, b, t, c, l, and f are as in the alg orithm description above. It is assumed that int reprents a type sufficient to hold values with w bits:
下⾯⼀段伪代码实现了通⽤的马特赛特算法，常量w, n, m, r, a, u, d, s, b, t, c, l, 和 f如上边算法中描述的⼀样。这⾥假设整型代表了⼀种带有w位值得类型后缀。
