梅森旋转算法

梅森旋转演算法（Mersenne twister）是一个。由和西村拓士在1997年开发，基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数，修正了古典随机数发生算法的很多缺陷。

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

 应用 
梅森旋转算法是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位整数序列。具有以下的优点：

 周期非常长，达到219937−1。尽管如此长的周期并不必然意味着高质量的伪随机数，但短周期（比如许多旧版本软件包提供的232）确实会带来许多问题。注：219937约等于4.3×106001，这个值比可观测宇宙内粒子总数的估计值（1087）还要高出上千个数量级。
 在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 的缓存空间。2011年，松本真和西村拓士针对这一问题提出了一个更小的版本，仅占127 bits的 TinyMT （Tiny Mersenne Twister）。

 k-分布 
暂无

 其他选择

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

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

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

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

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

 相关代码 
下面的一段伪代码使用MT19937算法生成范围在[0, 232 − 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 是已确定的种子。

 SFMT 

实现
 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) 

Category:偽隨機數生成器
Category:日本發明
Category:带有伪代码示例的条目