跳转至导航跳转至搜索Mersenne Twister是一个伪随机数生成器（PRNG）。它是迄今为止使用最广泛的通用PRNG。 [1]它的名字源于以下事实：它的周期长度被选为梅森素数。
Mersenne Twister于1997年由松本诚（ja）和西村拓士（Takuji Nishimura）共同开发。 [2]它是专为纠正旧式PRNG中发现的大多数缺陷而设计的。
Mersenne Twister算法的最常用版本基于Mersenne prime 2 19937-1。 MT19937的标准实现使用32位字长。还有另一种使用64位字长MT19937-64的实现（具有五个变体[3]）。它会产生不同的顺序。
它在Apache Commons，[29]，标准C ++（自C ++ 11起），[30] [31]和Mathematica中也可用。 [32]许多程序库都提供了附加实现，包括Boost C ++库，[33] CUDA库，[34]和NAG数值库。 [35]
Mersenne Twister是SPSS中的两个PRNG之一：保留另一个生成器仅是为了与较旧的程序兼容，而Mersenne Twister被称为“更可靠”。 [36] Mersenne Twister同样是SAS中的PRNG之一：其他生成器较旧且已弃用。 [37] Mersenne Twister是Stata中的默认PRNG，另一个是KISS，用于与较早版本的Stata兼容。 [38]
通过大量统计随机性测试，包括Diehard测试和大多数（但不是全部）TestU01测试。 [39]
2 19937-1的很长的周期。请注意，虽然长周期不能保证随机数生成器的质量，但短周期（例如许多较旧的软件包中常见的2 32）可能会出现问题。 [40]
每1≤k≤623将k分配为32位精度（有关k分配的定义，请参见下文）
实现通常比真正的随机方法更快地创建随机数。一项研究发现，Mersenne Twister创建的64位浮点随机数比硬件实现的基于处理器的RDRAND指令集快约二十倍。 [41]
除非使用TinyMT变体（如下所述），否则状态缓冲区相对较大，为2.5 KiB。
在TestU01套件的Crush和BigCrush中展示了两个明显的故障（线性复杂度）。像Mersenne Twister一样，该测试也基于F 2代数。 [39]还有许多其他通过所有测试的生成器（许多生成器严重失败）[需要澄清]。
尽管存在选择多组参数值的方法，但是仅种子值（但其他参数没有）不同的多个实例通常不适用于需要独立随机数生成器的蒙特卡洛模拟。 [43] [44]
扩散差：如果初始状态是高度非随机的，尤其是如果初始状态有很多零，则开始生成通过随机性测试的输出会花费很长时间。这样做的结果是，生成器的两个实例从几乎相同的初始状态开始，通常会在多次迭代之前输出几乎相同的序列进行多次迭代，然后最终发散。 MT算法的2002年更新改进了初始化功能，因此从这种状态开始的可能性很小。 [45]据说GPU版本（MTGP）更好。 [46]
包含0到1的子序列。这增加了较差的扩散性质，从而使得难以从多零状态恢复。
除非使用CryptMT变体（如下所述），否则不是加密安全的。原因是观察到足够多的迭代次数（在MT19937中为624，因为这是产生未来迭代次数的状态向量的大小），因此可以预测所有未来迭代次数。
备用生成器WELL（Well等距分布式长周期线性）可以提供更快的恢复速度，相等的随机性和几乎相等的速度。 [47]
64位MELG（具有梅森素数周期的64位最大均衡F 2线性发生器）在k分布特性方面得到了完全优化。 [49]
ACORN系列（于1989年发布）是另一个k分布的PRNG，它显示了与MT相似的计算速度，并且由于它满足当前（2019年）所有TestU01标准，因此具有更好的统计特性；与适当的参数选择一起使用时，ACORN可以具有较长的周期和精度。
PCG系列是一种更现代的长期生成器，具有更好的缓存局部性，并且使用现代分析方法可检测到的偏差较小。 [50]
如果满足以下条件，则将周期P的w位整数的伪随机序列x i称为k分布，以v位精度表示。
令trunc v（x）表示x的前v个位形成的数字，并考虑k个v位向量（trunc v（xi），trunc v（xi + 1），...，trunc v（ xi + k − 1））（0≤i＆lt; P）{\ displaystyle（{\ text {trunc}} _ {v}（x_ {i}），\，{\ text {trunc}} _ {v} （x_ {i + 1}），\，...，\，{\ text {trunc}} _ {v}（x_ {i + k-1}））\ quad（0 \ leq i＆lt; P）} 。
然后，2 kv可能的比特组合中的每一个在一个周期内发生相同的次数，但全零组合的发生频率降低一次。
对于w位的字长，Mersenne Twister生成范围为[0，2 w-1]的整数。
Mersenne Twister算法基于有限二进制场F 2上的矩阵线性递归。该算法是有理规范形式（TGFSR（R））的扭曲广义反馈移位寄存器[51]（扭曲GFSR或TGFSR），具有状态位反射和回火。基本思想是通过简单的递归关系定义系列xi {\ displaystyle x_ {i}}，然后输出形式为xi T {\ displaystyle x_ {i} T}的数字，其中T {\ displaystyle T}为一个称为回火矩阵的可逆F 2矩阵。
通用算法的特征在于以下数量（其中一些解释只有在阅读了其余算法后才有意义）：
m：中间词，在定义系列x的递归关系中使用的偏移，1≤m＜1。 ñ
r：一个字的分离点，或低位掩码的位数，0≤r≤w-1
限制为2 nw-r-1是梅森素数。此选择简化了参数搜索中所需的本原性检验和k分布检验。
系列x定义为具有递归关系的一系列w位量：
xk + n：= xk + m⊕（（xku ∣∣ xk + 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 \ qquad k = 0,1，\ ldots}
其中∣ {\ displaystyle \ mid \ mid}表示位向量的连接（高位在左边），⊕{\ displaystyle \ oplus}按位异或（XOR），xku {\ displaystyle {x_ {k}} ^ {u}}表示xk {\ displaystyle x_ {k}}的高w − r {\ displaystyle wr}位，而xk +1 l {\ displaystyle x_ {k + 1} ^ {l}}表示低位xk的r {\ displaystyle r}位+ 1 {\ displaystyle x_ {k + 1}}。扭曲变换A以有理范式定义为：
A =（0 I w − 1 aw − 1（aw − 2，…，a 0））{\ displaystyle A = {\ begin {pmatrix} 0＆amp; I_ {w-1} \\ a_ {w-1}＆amp ;（a_ {w-2}，\ ldots，a_ {0}）\ end {pmatrix}}}
以I n-1作为（n-1）×（n-1）单位矩阵。有理范式的好处是可以将A的乘法有效地表示为：（请记住，矩阵乘法是在F 2中完成的，因此按位XOR代替了加法）
x A = {x 1 x 0 = 0（x 1）x ax 0 = 1 {\ displaystyle {\ boldsymbol {x}} A = {\ begin {cases} {\ boldsymbol {x}} \ gg 1＆amp; x_ {0} = 0 \\（{\ boldsymbol {x}} \ gg 1）\ oplus {\ boldsymbol {a}}＆amp; x_ {0} = 1 \ end {cases}}}
像TGFSR（R）一样，Mersenne Twister通过回火变换进行级联，以补偿均布尺寸的减小（因为选择A为有理正态形式）。请注意，这等效于使用矩阵A {\ displaystyle A}，其中A = T − 1 AT {\ displaystyle A = T ^ {-1} AT}对于T {\ displaystyle T}是可逆矩阵，因此需要进行分析下面提到的特征多项式仍然成立。
与A一样，我们选择一个易于计算的回火变换，因此实际上并不构造T本身。对于Mersenne Twister，回火定义为
其中x是该序列中的下一个值，y是临时中间值，z是从算法返回的值，其中＆lt;＆lt ;,＆gt;当按位向左和向右移动时，＆amp;作为按位和。添加了第一个和最后一个转换，以改善低位均等分布。根据TGFSR的性质，需要s + t≥w / 2⌋− 1 {\ displaystyle s + t \ geq \ lfloor w / 2 \ rfloor -1}才能达到较高位的均分上限。
请注意，Mersenne Twister的32位实现通常具有d = FFFFFFFF 16.结果是，算法说明中有时会省略d，因为在这种情况下按位和d无效。
Mersenne Twister实现所需的状态是n个值（每个w位）的数组。为了初始化数组，使用w位的种子值通过将x 0设置为种子值并随后进行设置来提供x 0到x n−1
x i = f×（x i-1⊕（x i-1＆gt;＆gt;（w-2）））+ i
因为我从1到n-1该算法然后生成的第一个值基于x n，而不是x0。常数f构成了生成器的另一个参数，尽管不是算法本身的一部分。 MT19937的f值为1812433253，MT19937-64的f值为6364136223846793005。[52]
为了在T GFSR中达到2 nw − r − 1周期的理论上限，φB（t）必须是一个原始多项式，φB（t）是T的特征多项式
B =（0 I w 0 0 0 I w 0 0 0 0 0 I w − r S 0 0 0）←第m行{\ displaystyle B = {\ begin {pmatrix} 0＆amp; I_ {w}＆amp; \ cdots＆amp; 0＆amp; 0 \\\ vdots＆amp;＆amp;＆amp; \\ I_ {w}＆amp; \ vdots＆amp; \ ddots＆amp; \ vdots＆amp; \ vdots \\\ vdots＆amp;＆amp;＆amp; \\ 0＆amp; 0＆amp; \ cdots＆amp; I_ {w}＆amp; 0 \\ 0＆amp; 0＆amp; \ cdots＆amp; 0＆amp; I_ {wr} \\ S＆amp; ; 0＆amp; \ cdots＆amp; 0＆amp; 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＆amp; I_ {r} \\ I_ {w-r}＆amp; 0 \ end {pmatrix}} A}
该周期达到理论上限2 nw-r-1（除非初始化为0）
n个维度的均等分布（例如线性同余生成器最多可以管理5个维度的合理分布）
以下伪代码实现了通用的Mersenne Twister算法。常数w，n，m，r，a，u，d，s，b，t，c，l和f与上面的算法描述相同。假定int表示足以容纳w位值的类型：
//创建一个长度为n的数组，以存储生成器int [0 .. n-1] MT int索引的状态：= n + 1 const int lower_mask =（1＆lt;＆lt; r）-1 // r 1的二进制数const int upper_mask =（not notlow_mask）的最低w位//通过种子函数seed_mt（int seed）{索引初始化：生成器； n MT [0]：= i的种子从1到（n-1）{//遍历每个元素MT [i]：=（f *（MT [i-1] xor（MT [i-1]＆gt;＆gt;（w- 2）））+ i）}} //基于MT [index]提取一个调节值//每n个数字调用twist（）函数extract_number（）{如果index＆gt; = n {如果index＆gt; n {错误＆＃34;发电机从未播种＆＃34; //或者，使用恒定值的种子； 5489用于参考C代码[53]} twist（）} int y：= MT [index] y：= y xor（（y＆gt; u）and d）y：= y xor（（y＆lt; ＆lt; s）和b）y：= y xor（（y＆lt; t）和c）y：= y xor（y＆gt; l）index：= index + 1返回（y的最低w位）} //从系列x_i函数twist（）{为i从0到（n-1）{int x :: =（MT [i] and upper_mask）+（MT [（i + 1） mod n]和Lower_mask）int xA：= x＆gt;＆gt; 1 if（x mod 2）！= 0 {// x的最低位是1 xA：= xA xor a} MT [i] :: MT [（i + m）mod n] xor xA} index：= 0}
考虑下面的Python 3数值实现，该实现使用Mersenne素数2 ^ 31-1。它公开了两个公共成员，用于生成浮点数和整数，或其中之一的数组：
来自警告导入警告类Mersenne：伪随机数生成器伪随机数生成器def __init__（self，seed = 1234）：＆＃34;＆＃34;＆＃34;初始化伪随机数生成器。接受整数或浮点种子，该种子与整数乘数k和梅森素数j一起用于“ twist”。后者中的伪随机数。该成员还初始化生成器周期的顺序，以便在生成将要循环时，浮动成员和整数成员可以发出警告，因此不再是伪随机的。 ＆＃34;＆＃34;＆＃34;自我。种子=种子自我。 j = 2 ** 31-1个自我。 k = 16807自我。 period = 2 ** 30 def float（self，interval = None，count = 1）：＆＃34;＆＃34;＆＃34;返回一个伪随机浮点数。默认值为一个介于零和一之间的浮点数。传入元组或列表（a，b），以返回[a，b]上的浮点数。如果count为1，则返回一个数字，否则返回一个数字列表。 ＆＃34;＆＃34;＆＃34;结果= []，表示i在范围（计数）：self中。种子=（自我。k *自我。种子）％自我。 j如果interval不为None：结果。 append（（interval [1]-interval [0]）*（self.seed / self.j）+ interval [0]）else：结果。追加（自我。种子/自我。j）自我。周期-= 1，如果self。 period == 0：如果count == 1，则发出警告（伪随机周期即将到来！！，类别= ResourceWarning）：返回结果。 pop（）else：返回结果def整数（self，interval = None，count = 1）：＆＃34;＆＃34;＆＃34;返回一个伪随机整数。默认值为{0,1}中的一个整数。传入元组或列表（a，b），以返回[a，b]上的整数。如果count为1，则返回一个数字，否则返回一个数字列表。 ＆＃34;＆＃34;＆＃34;结果= []，表示i在范围（计数）：self中。种子=（自我。k *自我。种子）％自我。 j如果interval不为None：结果。 append（int（（interval [1]-interval [0] +1）*（self.seed / self.j）+ interval [0]））否则：result = self。种子/自我。如果结果＆lt; 0.50：结果。追加（0）else：结果。追加（1）自我。周期-= 1，如果self。 period == 0：如果count == 1，则发出警告（伪随机周期即将到来！！，类别= ResourceWarning）：返回结果。 pop（）else：返回结果
CryptMT是一种流密码和加密安全的伪随机数生成器，它在内部使用Mersenne Twister。 [54] [55]它是由松本和西村与Ha田麻里子和斋藤睦夫一起开发的。它已提交到eCRYPT网络的eSTREAM项目。 [54]与Mersenne Twister或其其他派生产品不同，CryptMT已获得专利。
MTGP是Mersenne Twister的变体，它针对Saito Mutsuo Saito和Makoto Matsumoto发布的图形处理单元进行了优化。 [56]从MT扩展了基本的线性递归操作，并选择了参数以允许许多线程并行计算递归，同时共享它们的状态空间以减少内存负载。该论文声称，对于5×10 7个随机32位整数，非常老的4.7 ms的GPU（具有192个内核的Nvidia GTX260）具有更好的MT分布和性能。
SFMT（面向SIMD的快速Mersenne Twister）是Mersenne Twister的一种变体，于2006年推出[57]，设计为在128位SIMD上运行时速度很快。
它具有比MT更好的v位精度的等值分配属性，但比WELL（＆＃39; Well等值分配的长周期线性＆＃39;）更差。
SFMT支持Intel SSE2和PowerPC AltiVec。它也可用于PlayStation 3中带有Cell BE的游戏。[59]
TinyMT是由Saito和Matsumoto在2011年提出的Mersenne Twister的变体。[60] TinyMT仅使用127位状态空间，与原始的2.5 KiB状态相比，显着减少。但是，它的周期为2 127-1，比原始周期短得多，因此只有在内存非常宝贵的情况下，作者才建议这样做。
^例如Marsland S.（2011）机器学习（CRC Press），第4.1.1节。另请参阅“软件系统中的采用”部分。
^松本M. Nishimura，T。（1998）。梅森捻线器：一个623维均匀分布的均匀伪随机数生成器。 （PDF）。 ACM建模和计算机仿真交易。 8（1）：3-30。 CiteSeerX 10.1.1.215.1141。 doi：10.1145 / 272991.272995。 S2CID 3332028。
^约翰·萨瓦德。 ＆＃34; The Mersenne Twister＆＃34;。随后的论文发表于2000年，给出了5种形式的Mersenne Twister，周期为2 ^ 19937-1。所有这五个都设计为使用64位算术而不是32位算术实现。
^Mélard，G.（2014），＆＃34;关于Microsoft Excel 2010中的统计程序的准确性＆＃34 ;,计算统计，29（5）：1095–1128，CiteSeerX 10.1.1.455.5508，doi：10.1007 / s00180-014-0482-5，S2CID 54032450。
^ a b P. L＆＃39; Ecuyer和R.Simard，＆＃34; TestU01：＆＃34;用于对随机数生成器进行经验测试的C库，＆＃39; ACM Transactions on Mathematical Software，第33、4和22条（2007年8月）。
^注：2 19937约为4.3×10 6001;这比可观察到的宇宙中估计的粒子数10 87大了多个数量级。
^ Route，马修（2017年8月10日）。 ＆＃34;放射火焰的Ultracool矮人种群合成。天体物理学杂志。 845（1）：66。arXiv：1707.02212。 Bibcode：2017ApJ ... 845 ... 66R。 doi：10.3847 / 1538-4357 / aa7ede。 S2CID 118895524。
^＆＃34;面向SIMD的快速Mersenne Twister（SFMT）：比Mersenne Twister＆＃34;快两倍。 日本科学促进会。 ^原本博; 松本诚; 西村隆司 弗朗索瓦·潘尼顿； Pierre L’Ecuyer。 ＆＃34; F2线性随机数生成器的有效跳台＆＃34; （PDF）。 ^ Fog，Agner（2015年5月1日）。 ＆＃34;用于矢量处理器和多核处理器的伪随机数生成器。 现代应用统计方法杂志。 14（1）：308–334。 doi：10.22237 / jmasm / 1430454120。 ^ P. L＆＃39; Ecuyer，＆＃34; Uniform Random Number Generators＆＃34 ;，国际统计科学百科全书，Lovric，Miodrag（Ed。），Spr ......