亂數產生器-Mersenne Twister Random Number Generator

出自KMU Wiki

'Mersenne Twister(簡稱MT''''):

   

在1998年由Makoto和Takuji提出的，是多重遞迴矩陣方法(MRMM)中的一種，MRMM是在F₂域上由線性遞推式:

產生隨機向量序列。X_k是列向量，Ai是Wx W矩陣。

    而MT演算法產生一個字(word)向量序列，看作是[0,2^w-1]間的均勻隨機整數。除以2^w-1，認為每個字向量為[0,1]的一個實數。 算法如下:

     n=遞推式的維數，0<=r(隱藏於X上標u下標k的定義中)<=w-1，1<=m<=n 。給出X₀,X₁,...X _n-1作為初始點，那麼X_n由上面的式子再k=0時產生，令k=1,2,...，亂數產生器逐步產生X_n+1,X_n+2,...，在式子的右邊，Xuk意味著X_k前w-r位，因此如果X=(X_w-1,X_w-2,...,X₀)，那麼由定義，X_u是w-r維向量(X_w-1,...,X_r)，X_t是r維向量(X_r-1,...,X₀)。因此(X上標u下標k | X上標t下標k+1)恰好是一個並列，即X_k前w-r位和X_k+1的後r位按順序並列再一起得到的一個向量。矩陣A乘在這個向量的右邊。(XOR舉例:1 XOR 1=0 XOR 0，1 XOR 0=0 XOR 1=1)

   

對於上式，如果r=0，它變為X_k+n = X_k+n XOR X_kA，即變成Matsumoto和Kurita提出的TGFSR。如果r=0且A=I，它又變為X_k+n = X_k+m XOR X_k，即Lewis和Payne提出的GFSR。

   為了使乘A計算速度較快，選擇

那麼計算XA可僅僅使用位運算：

    MT有以下優點:隨機性好，在計算機上容易實現，佔用記憶體較少(mt19937的C程式碼執行僅需624個字的工作區)，與其它已使用的亂數產生器相比，產生隨機數的速度快、週期長，可達到2¹⁹⁹³⁷-1，且具有623維均勻分布的性質。

    雖然MT在許多方面較其他產生器優越，但它還是有一些缺點，即它所產生的序列是

高維均勻性的，還不夠完善。