梅森旋转算法

维基百科，自由的百科全书
跳转至： 导航、 搜索

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

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

目录

应用 [编辑]

优点 [编辑]

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

  1. 有219937 − 1的非常长的周期。在许多软件包中的短周期—232 随机数产生器在一个长周期中不能保证生成随机数的质量。[2]
  2. 在1 ≤ k ≤ 623的维度之间都可以均等分布(参见定义).
  3. 除了在统计学意义上的不正确的随机数生成器以外， 在所有伪随机数生成器法中是最快的(当时)[3]

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) // 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)) // 0x9d2c5680
     y := y xor (left shift by 15 bits(y) and (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) // 0x9908b0df
         }
     }
 }

SFMT [编辑]

实现 [编辑]

参考列表 [编辑]

  1. ^ Matsumoto, M.; Nishimura, T. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation. 1998, 8 (1): 3–30. doi:10.1145/272991.272995.  编辑
  2. ^ Note: 219937 is approximately 4.3 × 106001; this is many orders of magnitude larger than the estimated number of particles in the observable universe, which is 1087.
  3. ^ 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.

外部链接 [编辑]

来自“http://zh.wikipedia.org/w/index.php?title=梅森旋转算法&oldid=26578529”