梅森旋转算法

梅森旋转算法Mersenne twister)是一个伪随机数发生算法英语Pseudorandom number generator。由松本真日语松本真西村拓士[1]在1997年开发,基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数,修正了古典随机数发生算法的很多缺陷。

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

应用

梅森旋转算法是RPythonRubyIDLFree PascalPHPMapleMatlabGNU多重精度运算库和GSL的默认伪随机数产生器。从C++11开始,C++也可以使用这种算法。在Boost C++,Glib和NAG数值库中,作为插件提供。

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

优点

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

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

缺点

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

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

实现

参考列表

  1. ^ Makoto Matsumoto, Takuji Nishimura. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation (TOMACS). 1998-01-01, 8 (1): 3–30 [2018-04-02]. ISSN 1049-3301. doi:10.1145/272991.272995. 
  2. ^ 注:219937约等于4.3×106001,这个值比可观测宇宙内粒子总数的估计值(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.
  4. ^ Tiny Mersenne Twister (TinyMT). hiroshima-u.ac.jp. [4 October 2015]. (原始内容存档于2020-07-11). 

外部链接