梅森旋转算法

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

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

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

1. 周期非常长，达到2¹⁹⁹³⁷−1。尽管如此长的周期并不必然意味着高质量的伪随机数，但短周期（比如许多旧版本软件包提供的2³²）确实会带来许多问题。^[2]
2. 在1 ≤ k ≤ 623的维度之间都可以均等分布（参见定义）。
3. 除了在统计学意义上的不正确的随机数生成器以外，在所有伪随机数生成器法中是最快的（当时）^[3]

为了性能，这个算法付出了巨大的空间成本（当时而言）：需要 2.5 KiB 的缓存空间。2011年，松本真和西村拓士针对这一问题提出了一个更小的版本，仅占127 bits的 TinyMT （Tiny Mersenne Twister）。^[4]

暂无

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

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

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

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

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

下面的一段伪代码使用MT19937算法生成范围在[0, 2³² − 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 (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 (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 代码

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

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

实现

• XLL Excel Addin Implementation of mersenne twister random number generator （页面存档备份，存于互联网档案馆）
• Two implementations of Mersenne Twister in Java: one is the fastest known, and the other is a drop-in replacement for java.util.Random （页面存档备份，存于互联网档案馆）
• The GNU Scientific Library (GSL), containing an implementation of the Mersenne Twister （页面存档备份，存于互联网档案馆）
• C++ and binary function libraries for several platforms. Multithreaded. Includes Mersenne Twister and SFMT （页面存档备份，存于互联网档案馆）
• Implementations of the Mersenne Twister in C and C++ （页面存档备份，存于互联网档案馆）
• Implementation of the Mersenne Twister in C++
• Implementation of the Mersenne Twister in C++ within the Mobile Robot Programming Toolkit
• Implementation of Mersenne Twister as an add-in for Microsoft Excel （页面存档备份，存于互联网档案馆）
• 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 （页面存档备份，存于互联网档案馆）
• Implementation of Mersenne Twister for REALbasic (requires REALbasic 2006r1 or greater)
• Implementation of Mersenne Twister for Lisp
• Implementation of Mersenne Twister in Euphoria
• Implementation of Mersenne Twister for C# (newer, System.Random drop-in replacement) （页面存档备份，存于互联网档案馆） (Older implementation)
• Implementation of Mersenne Twister for Ada
• Implementation of Mersenne Twister for Fortran 95
• Implementation of Mersenne Twister for Mathematica
• Implementation of Mersenne Twister for MATLAB （页面存档备份，存于互联网档案馆）
• Implementation of Mersenne Twister for Mitrion-C （页面存档备份，存于互联网档案馆）
• Implementation of Mersenne Twister for Clean
• High-speed Implementation of Mersenne Twister （页面存档备份，存于互联网档案馆） in Linoleum (a cross-platform Assembler), by Herbert Glarner
• CPAN module implementing the Mersenne Twister for use with Perl （页面存档备份，存于互联网档案馆）
• Implementation of Mersenne Twister for Haskell （页面存档备份，存于互联网档案馆）
• Implementation of Mersenne Twister for Standard ML
• Implementation of Mersenne Twister in F#
• It also is implemented in gLib and the standard libraries of at least PHP, Python and Ruby.
• RandomLib （页面存档备份，存于互联网档案馆） C++ library implementing Mersenne Twister and SFMT.
• C++ implementation of Mersenne Twister for the IBM/Sony Cell Broadband Engine (Cell BE) specialized processing units
• Mersenne Twister ported to ActionScript
• Mersenne Twister in Clojure （页面存档备份，存于互联网档案馆）
• Implementation of Mersenne Twister for ABAP （页面存档备份，存于互联网档案馆）

• The academic paper for MT, and related articles by Makoto Matsumoto （页面存档备份，存于互联网档案馆）
• Mersenne Twister home page, with codes in C, Fortran, Java, Lisp and some other languages
• SIMD-oriented Fast Mersenne Twister (SFMT) （页面存档备份，存于互联网档案馆）