MersenneTwister算法

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%)。

相關詞條

相關搜尋

熱門詞條

聯絡我們