MersenneTwister算法

Mersenne twister算法譯為馬特賽特旋轉演算法，是偽隨機數發生器之一，其主要作用是生成偽隨機數。此算法是Makoto Matsumoto (松本)和Takuji Nishimura (西村)於1997年開發的，基於有限二進制欄位上的矩陣線性再生。可以快速產生高質量的偽隨機數，修正了古老隨機數產生算法的很多缺陷。 Mersenne Twister這個名字來自周期長度通常取Mersenne質數這樣一個事實。常見的有兩個變種Mersenne Twister MT19937和Mersenne Twister MT19937-64。
Mersenne Twister算法的原理：Mersenne Twister算法是利用 線性反饋移位暫存器( LFSR)產生隨機數的，LFSR的反饋函式是暫存器中某些位的簡單異或，這些位也稱之為抽頭序列。一個n位的LFSR能夠在重複之前產生2^n-1位長的偽隨機序列。只有具有一定抽頭序列的LFSR才能通過所有2^n-1個內部狀態，產生2^n - 1位長的偽隨機序列，這個輸出的序列就稱之為 M序列。為了使LFSR成為最大周期的LFSR，由抽頭序列加上常數1形成的多項式必須是本原多項式。一個n階本原多項式是不可約多項式，它能整除x^(2*n-1)+1而不能整除x^d+1，其中d能整除2^n-1。例如(32,7,5,3,2,1,0)是指本原多項式x^32+x^7+x^5+x^3+x^2+x+1，把它轉化為最大周期LFSR就是在LFSR小鄧第32，7，5，2，1位抽頭。利用上述兩種方法產生周期為m的偽隨機序列後，只需要將產生的偽隨機序列除以序列的周期，就可以得到(0，1)上均勻分布的偽隨機序列了。
Mersenne Twister有以下優點：隨機性好，在計算機上容易實現，占用記憶體較少(mt19937的C程式碼執行僅需624個字的工作區域)，與其它已使用的偽隨機數發生器相比，產生隨機數的速度快、周期長，可達到2^19937-1，且具有623維均勻分布的性質，對於一般的套用來說，足夠大了，序列關聯比較小，能通過很多隨機性測試。
馬特賽特旋轉演算法產生一個偽隨機數，一般為MtRand()。下面列舉Mersenne Twister算法的幾個例子。
例一：顯示0-4之間的一個隨機整數
print (math.floor (MtRand () * 5))
例二：產生100萬個隨機數
MtSrand (1234567) -- 設定隨機數產生器使用的種子
for j = 1, 1000000 do
table.insert (nums, MtRand ())
例三：用Mersenne Twister算法模擬扔硬幣的程式
heads = 0
tails = 0
for j = 1, 1000000 do
i = math.floor (MtRand () * 2)
if i == 0 then
heads = heads + 1
else
tails = tails + 1
end -- if
end -- for
print ("heads = ", heads) --> 498893
print ("tails = ", tails) --> 501107
通過模擬扔 1000000 次硬幣，我們這次得到了 498893 次正面，501107 次背面（正面占總次數的 49.8893%）。