梅森旋转算法

**梅森旋轉演算法**（**Mersenne twister**）是一個偽隨機數發生算法。由松本眞和西村拓士在 1997 年開發，基於有限二進位欄位上的矩陣線性遞歸 $F_{2}$ 。可以快速產生高品質的偽隨機數，修正了古典隨機數發生算法的很多缺陷。

Mersenne Twister 這個名字來自周期長度取自梅森質數的這樣一個事實。這個算法通常使用兩個相近的變體，不同之處在於使用了不同的梅森素數。一個更新的和更常用的是 MT19937, 32 位字長。還有一個變種是 64 位版的 MT19937-64。對於一個 _k_ 位的長度，Mersenne Twister 會在 $[0,2^{k}-1]$ 的區間之間生成離散型均勻分布的隨機數。

## 應用

梅森旋轉算法是 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. 周期非常長，達到 219937−1。儘管如此長的周期並不必然意味著高品質的偽隨機數，但短周期（比如許多舊版本軟體包提供的 232）確實會帶來許多問題。
2. 在 1 ≤ _k_ ≤ 623 的維度之間都可以均等分布（參見定義）。
3. 除了在統計學意義上的不正確的隨機數生成器以外，在所有偽隨機數生成器法中是最快的（當時）

## 缺點

為了性能，這個算法付出了巨大的空間成本（當時而言）：需要 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 代碼

調用函數 `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) （頁面存檔備份，存於網際網路檔案館）