查看“︁梅森旋转算法”︁的源代码

{{Expand language|1=en|time=2021-11-01T20:39:58+00:00}}
{{NoteTA
|1=zh-cn:质量;zh-tw:品質;
}}
'''梅森旋转演算法'''（'''Mersenne twister'''）是一个{{le|伪随机数发生算法|Pseudorandom number generator}}。由{{link-ja|松本眞|松本真}}和[[西村拓士]]<ref>{{cite journal|title=Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator|date=1998-01-01|journal=ACM Transactions on Modeling and Computer Simulation (TOMACS)|volume=8|issue=1|doi=10.1145/272991.272995|pages=3–30|issn=1049-3301|url=http://dl.acm.org/citation.cfm?id=272991.272995|accessdate=2018-04-02|author=Makoto Matsumoto, Takuji Nishimura}}</ref>在1997年开发，基于有限[[二进制]][[字段]]上的[[矩阵线性递归]]<math>F_{2}</math>。可以快速产生高质量的伪随机数，修正了古典随机数发生算法的很多缺陷。

Mersenne Twister这个名字来自周期长度取自[[梅森質數]]的这样一个事实。这个算法通常使用两个相近的变体，不同之处在于使用了不同的梅森素数。一个更新的和更常用的是MT19937, 32位字长。还有一个变种是64位版的MT19937-64。对于一个''k''位的长度，Mersenne Twister会在<math>[0,2^k-1]</math>的区间之间生成[[离散型均匀分布]]的随机数。

== 应用 ==
梅森旋转算法是[[R]]、[[Python]]、[[Ruby]]、[[IDL (编程语言)|IDL]]、[[Free Pascal]]、[[PHP]]、[[Maple]]、[[Matlab]]、[[GNU多重精度运算库]]和GSL的默认伪随机数产生器。从C++11开始，C++也可以使用这种算法。在Boost C++,Glib和NAG数值库中，作为插件提供。

在SPSS中，梅森旋转算法是两个PRNG中的一个：另一个是产生器仅仅为保证旧程序的兼容性，梅森旋转被描述为“更加可靠”。梅森旋转在SAS中同样是PRNG中的一个，另一个产生器是旧时的且已经被弃用。

==优点==

最为广泛使用Mersenne Twister的一种变体是MT19937，可以产生32位整数序列。具有以下的优点：

# 周期非常长，达到2<sup>19937</sup>−1。尽管如此长的周期并不必然意味着高质量的伪随机数，但短周期（比如许多旧版本软件包提供的2<sup>32</sup>）确实会带来许多问题。<ref>注：2<sup>19937</sup>约等于4.3×10<sup>6001</sup>，这个值比[[可觀測宇宙|可观测宇宙]]内粒子总数的估计值（10<sup>87</sup>）还要高出上千个数量级。</ref>
# 在1 ≤ ''k'' ≤ 623的维度之间都可以均等分布（参见定义）。
# 除了在统计学意义上的不正确的随机数生成器以外，在所有伪随机数生成器法中是最快的（当时）<ref>P. L'Ecuyer and R. Simard, ``TestU01: A C Library for Empirical Testing of Random Number Generators'', ACM Transactions on Mathematical Software, 33, 4, Article 22, August 2007.</ref>

==缺点==

为了性能，这个算法付出了巨大的空间成本（当时而言）：需要 2.5 [[KiB]] 的[[memory hierarchy|缓存]]空间。2011年，[[松本真]]和[[西村拓士]]针对这一问题提出了一个更小的版本，仅占127 bits的 TinyMT （Tiny Mersenne Twister）。<ref>{{cite web|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/index.html|title=Tiny Mersenne Twister (TinyMT)|work=hiroshima-u.ac.jp|accessdate=4 October 2015|archive-date=2020-07-11|archive-url=https://web.archive.org/web/20200711134837/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/index.html|dead-url=no}}</ref>

== ''k''-分布 ==
暂无

== 其他选择==

== 算法详细 ==
整个算法主要分为三个阶段：

第一阶段：获得基础的梅森旋转链；

第二阶段：对于旋转链进行旋转算法；

第三阶段：对于旋转算法所得的结果进行处理；

算法实现的过程中，参数的选取取决于梅森素数，故此得名。

== 相关代码 ==
下面的一段[[伪代码]]使用MT19937算法生成范围在[0, 2<sup>32</sup>&nbsp;&minus;&nbsp;1]的均匀分布的32位整数：

===偽代碼===
  ''//創建一個長度為624的數組來存儲發生器的狀態''
  '''int'''[0..623] MT
  '''int''' index = 0
  
  ''//初始化產生器，種子作為首項內容''
  '''function''' initialize_generator('''int''' seed) {
      i := 0
      MT[0] := seed
      '''for''' i '''from''' 1 '''to''' 623 { ''// 走訪剩下的每個元素''
          MT[i] := '''last 32 bits of'''(1812433253 * (MT[i-1] '''[[位操作#按位异或（XOR）|xor]]''' ('''right shift by 30 bits'''(MT[i-1]))) + i) ''// 1812433253 == 0x6c078965''
      }
  }
  
  ''// Extract a tempered pseudorandom number based on the index-th value,''
  ''// calling generate_numbers() every 624 numbers''
  '''function''' extract_number() {
      '''if''' index == 0 {
          generate_numbers()
      }
  
      '''int''' y := MT[index]
      y := y '''xor''' ('''right shift by 11 bits'''(y))
      y := y '''xor''' ('''left shift by 7 bits'''(y) '''[[位操作#按位与（AND）|and]]''' (2636928640)) ''// 2636928640 == 0x9d2c5680''
      y := y '''xor''' ('''left shift by 15 bits'''(y) '''and''' (4022730752)) ''// 4022730752 == 0xefc60000''
      y := y '''xor''' ('''right shift by 18 bits'''(y))
 
      index := (index + 1) '''[[模除|mod]]''' 624
      '''return''' y
  }
  
  ''// Generate an array of 624 untempered numbers''
  '''function''' generate_numbers() {
      '''for''' i '''from''' 0 '''to''' 623 {
          '''int''' y := (MT[i] & 0x80000000)                       // bit 31 (32nd bit) of MT[i]
                         + (MT[(i+1) '''mod''' 624] & 0x7fffffff)   // bits 0-30 (first 31 bits) of MT[...]
          MT[i] := MT[(i + 397) '''mod''' 624] '''xor''' ('''right shift by 1 bit'''(y))
          '''if''' (y '''mod''' 2) != 0 { ''// y is odd''
              MT[i] := MT[i] '''xor''' (2567483615) ''// 2567483615 == 0x9908b0df''
          }
      }
  }

===Python 代码===
<syntaxhighlight lang="python">
def _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)


    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)


    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df
</syntaxhighlight>

调用函数 <code>MT19937(''seed'').extract_number()</code> 将会返回随机数，其中 <code>''seed''</code> 是已确定的种子。

== SFMT ==

===实现===
* [http://www.pimpmyexcel.com/ XLL Excel Addin Implementation of mersenne twister random number generator] {{Wayback|url=http://www.pimpmyexcel.com/ |date=20090514065614 }}
* [http://www.cs.gmu.edu/~sean/research/ Two implementations of Mersenne Twister in Java: one is the fastest known, and the other is a drop-in replacement for java.util.Random] {{Wayback|url=http://www.cs.gmu.edu/~sean/research/ |date=20210203132427 }}
* [http://www.gnu.org/software/gsl/ The GNU Scientific Library (GSL), containing an implementation of the Mersenne Twister] {{Wayback|url=http://www.gnu.org/software/gsl/ |date=20050609001819 }}
* [http://www.agner.org/random/ C++ and binary function libraries for several platforms. Multithreaded. Includes Mersenne Twister and SFMT] {{Wayback|url=http://www.agner.org/random/ |date=20210330114202 }}
* [http://www.cs.hmc.edu/~geoff/mtwist.html Implementations of the Mersenne Twister in C and C++] {{Wayback|url=http://www.cs.hmc.edu/~geoff/mtwist.html |date=20200930032957 }}
* [https://web.archive.org/web/20080820051549/http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.html Implementation of the Mersenne Twister in C++]
* [https://web.archive.org/web/20100319165118/http://babel.isa.uma.es/mrpt/index.php/Example:Random_number_generation Implementation of the Mersenne Twister in C++] within the [[Mobile Robot Programming Toolkit]]
* [http://www.ntrand.com/ Implementation of Mersenne Twister as an add-in for Microsoft Excel] {{Wayback|url=http://www.ntrand.com/ |date=20200717043347 }}
* [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/BASIC/basic.html Implementation of Mersenne Twister as a free module for Visual Basic (Microsoft Excel, Microsoft Access and VB compilers) and for other Basic versions in the official site of the Mersenne Twister] {{Wayback|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/BASIC/basic.html |date=20200315115025 }}
* [https://web.archive.org/web/20080218152740/http://www.aaronballman.com/programming/REALbasic/Rand.php Implementation of Mersenne Twister for REALbasic (requires REALbasic 2006r1 or greater)]
* [https://web.archive.org/web/20100210230709/http://cybertiggyr.com/gene/jmt/ Implementation of Mersenne Twister for Lisp]
* [https://web.archive.org/web/20110715154716/http://www.rapideuphoria.com/mt.zip Implementation of Mersenne Twister in Euphoria]
* [http://code.msdn.microsoft.com/MersenneTwister Implementation of Mersenne Twister for C# (newer, System.Random drop-in replacement)] {{Wayback|url=http://code.msdn.microsoft.com/MersenneTwister |date=20101205060400 }} ([https://web.archive.org/web/20070110182320/http://www.c-sharpcorner.com/Code/2003/April/MersenneTwisterAlgo.asp Older implementation])
* [https://web.archive.org/web/20100508091716/http://adrianhoe.com/adrianhoe/projects/adamt19937/ Implementation of Mersenne Twister for Ada]
* [https://web.archive.org/web/20100411090930/http://www.coyotegulch.com/products/libcoyotl/twisted_road/index.html Implementation of Mersenne Twister for Fortran 95]
* [https://web.archive.org/web/20090110142338/http://modp.com/release/mma_mersenne_twister/ Implementation of Mersenne Twister for Mathematica]
* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6614&objectType=file Implementation of Mersenne Twister for MATLAB] {{Wayback|url=http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6614&objectType=file |date=20080924002704 }}
* [http://www.mitrionics.com/?page=page49058d1d215e8 Implementation of Mersenne Twister for Mitrion-C] {{Wayback|url=http://www.mitrionics.com/?page=page49058d1d215e8 |date=20090115194926 }}
* [https://web.archive.org/web/20100410193201/http://clean.cs.ru.nl/Download/Download_Libraries/mt/body_mt.html Implementation of Mersenne Twister for Clean]
* [http://herbert.gandraxa.com/herbert/rng.asp High-speed Implementation of Mersenne Twister] {{Wayback|url=http://herbert.gandraxa.com/herbert/rng.asp |date=20200109125401 }} in [[Linoleum programming language|Linoleum]] (a cross-platform [[Assembly language|Assembler]]), by Herbert Glarner
* [http://search.cpan.org/search?module=Math%3A%3ARandom%3A%3AMT%3A%3AAuto CPAN module implementing the Mersenne Twister for use with Perl] {{Wayback|url=http://search.cpan.org/search?module=Math%3A%3ARandom%3A%3AMT%3A%3AAuto |date=20170325052506 }}
* [http://www.augustsson.net/Darcs/MT/ Implementation of Mersenne Twister for Haskell] {{Wayback|url=http://www.augustsson.net/Darcs/MT/ |date=20100520022728 }}
* [https://web.archive.org/web/20080927225229/http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/org/mlton/ville/mersenne-twister/unstable/ Implementation of Mersenne Twister for Standard ML]
* [https://web.archive.org/web/20091010234544/http://mbishop.esoteriq.org/code/Fsharp/mt.fs Implementation of Mersenne Twister in F#]
* It also is implemented in [[gLib]] and the standard libraries of at least [[PHP]], [[Python]] and [[Ruby programming language|Ruby]].
* [http://randomlib.sourceforge.net RandomLib] {{Wayback|url=http://randomlib.sourceforge.net/ |date=20180612005302 }} C++ library implementing Mersenne Twister and SFMT.
* [https://web.archive.org/web/20081225142451/http://adam.ierymenko.name/files/MersenneTwister32_spe.cpp C++ implementation of Mersenne Twister for the IBM/Sony Cell Broadband Engine (Cell BE) specialized processing units]
* [https://web.archive.org/web/20100227093329/http://flashexperiments.insh-allah.com/#Mersenne_Twister_ported_to_ActionScript Mersenne Twister ported to ActionScript]
* [http://www.hackinghat.com/index.php/lisp/mersenne-twister-in-clojure Mersenne Twister in Clojure] {{Wayback|url=http://www.hackinghat.com/index.php/lisp/mersenne-twister-in-clojure |date=20190823002919 }}
* [http://help.sap.com/abapdocu_70/en/ABENCL_ABAP_MATH.htm Implementation of Mersenne Twister for ABAP] {{Wayback|url=http://help.sap.com/abapdocu_70/en/ABENCL_ABAP_MATH.htm |date=20160304222605 }}

==参考列表==
{{Reflist|2}}

== 外部链接==
* [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/earticles.html  The academic paper for MT, and related articles by Makoto Matsumoto] {{Wayback|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/earticles.html |date=20200803215540 }}
* [https://web.archive.org/web/20070828025507/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html Mersenne Twister home page, with codes in C, Fortran, Java, Lisp and some other languages]
* [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html SIMD-oriented Fast Mersenne Twister (SFMT)] {{Wayback|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html |date=20201109030227 }}
{{马兰·梅森}}
{{Authority control}}
[[Category:偽隨機數生成器]]
[[Category:日本發明]]
[[Category:带有伪代码示例的条目]]