隨機數計演算法比較,更好的隨機數對於程式是否真的值得。

• 2021 年 8 月 17 日
• 筆記
• C++, 測試, 演算法, 隨筆

隨機數計演算法比較,更好的隨機數對於程式是否真的值得。

本次,我們將評測四種隨機數生成法
測試語言為C++
測試有不嚴謹的地方歡迎提出。
本文僅僅發佈於部落格園

下面是他們時間表現

演算法介紹

庫函數rand

這個不用多說，cstdlib里的庫函數。

用的就是LCG(linear congruential generator)演算法

基於\(X(n+1) = (a * X(n) + c) \mod m\)​這樣的公式

下面的modrand就是手寫實現的這種演算法。

mt19937

也就是Mersenne Twister MT19937(馬特賽特旋轉演演算法)的實現。

基於有限二進位欄位上的矩陣線性再生。可以快速產生高品質的偽隨機數，修正了古老隨機數產生演算法的很多缺陷。

轉載自百度百科：

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維均勻分布的性質，對於一般的應用來說，足夠大了，序列關聯比較小，能通過很多隨機性測試。

xorshift32

int xorshift32()
{
    static int x(13147);
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

是一個比較複雜的數論問題,作者也不會。

modrand

看程式碼就知道是什麼原理了

unsigned int modrand()
{
    static int seed(13147);
    seed = (seed * 31 + 13) % ((1 << 31) - 1);
    return seed;
}

實際表現

上面的演算法,有的實現快,但是生成的品質不一定高，有的品質高，生成就更慢。

所以實際表現到底怎麼樣呢？

我將對下面的項目進行測試

上面兩個應該是隨機函數比較常見的應用了。

結果

FHQ_Treap(Rand生成速度將影響總時間,而隨機數的品質將影響樹高,也會影響總時間)

可以發現rand本身就夠用了,除非有特殊要求沒必要換用其他的函數。更沒必要自己手寫。