最近在做幀同步的實時對戰(zhàn)，要自己接管隨機數(shù)的產(chǎn)生，所以看了一下隨機數(shù)生成的相關(guān)算法。因為游戲會跑在不同平臺(iOS/Android)及不同硬件上，所以使用的算法有以下的要求：1. 不能依賴系統(tǒng)；2. 不能依賴硬件；3. 計算中不能使用浮點數(shù)(不同平臺不同硬件有可能結(jié)果不同)。再結(jié)合效率方面的考慮，最終選擇采用了線性同余算法，并在基礎(chǔ)上做了一定的加強。這篇博客主要記錄關(guān)于這個線性同余算法產(chǎn)生隨機數(shù)的一些思考。

首先要搞清楚隨機數(shù)的定義，真正的隨機數(shù)都不是計算出來的，這里我們說的隨機數(shù)其實都是偽隨機數(shù)，隨機數(shù)偽隨機數(shù)的定義，具體的論證等資料可以自行查閱。產(chǎn)生偽隨機數(shù)的算法有很多種，線性同余算法基于整數(shù)的加、乘和求模，算法簡單但是具有較強的規(guī)律性與周期性。怎么在這個基礎(chǔ)上盡量降低規(guī)律性與周期性，使得在更廣范圍內(nèi)覆蓋更多可能就是我們的目標。

首先要了解的是線性同余函數(shù)公式，最終結(jié)果受乘數(shù)λ，加數(shù)C和模數(shù)M決定。M通常我們會使用一個較大的素數(shù)，而λ,C的選取在很大程度上會影響生成的隨機數(shù)的質(zhì)量。我們嘗試使用不同的λ與C去生成一系列的隨機數(shù)并觀察他們。為了直觀感受一些列的隨機數(shù)是否足夠隨機，我們用這些數(shù)字作為X,Y填充一張1024 * 512的位圖，觀察圖上的點的位置，可以得知這一系列隨機數(shù)在1024 * 512范圍內(nèi)隨機分布的情況。

使用最基礎(chǔ)的線性同余公式生成的隨機數(shù)，因乘數(shù)λ、加數(shù)C參數(shù)不同，有的時候比較隨機(圖一)，有的時候呈現(xiàn)出比較強的規(guī)律性(圖二)，但周期性都是十分短。在多次嘗試中能成功填充的點從幾千到幾萬個，但并不能完全填充整張圖，證明周期性在1024*512種組合中都無法確保不重復。這樣的隨機數(shù)算法顯然是不夠好的。要在線性同余算法的基礎(chǔ)上加強，首先想到的是計算Xn時，不再只用Xn-1參與，而是用X1到Xn-1的加和。

使用加和版本的線性同余算法，套用不同的參數(shù)λ、C再次生成隨機數(shù)填充位圖觀察：

可以看出加和版本的線性同余算法產(chǎn)生的隨機數(shù)，因乘數(shù)λ、加數(shù)C參數(shù)不同，有的時候呈現(xiàn)出比較強的規(guī)律性(圖三)，有的時候比較隨機(圖四)。數(shù)量上從10w到50w不等，大部分情況無法覆蓋1024*512種情況，極少數(shù)情況下能完全覆蓋。選取一組較好的λ,C參數(shù)，使用加和版本的線性同余算法產(chǎn)生的隨機數(shù)其實已經(jīng)可以滿足游戲功能的需求了，如果還想加再優(yōu)化，則要從參數(shù)λ,C的變化入手。

在多次測量的過程中，用不同的參數(shù)λ,C能得出不同的表現(xiàn)，那只要λ,C不再取固定值，就相當于混合了使用多個加和線性同余算法生成結(jié)果的混合來做隨機數(shù)。這樣做即使一組λ,C生成的隨機數(shù)有一定的周期性與規(guī)律性，但混用多組結(jié)果，就能把周期性與規(guī)律性再次降低(但無法消除)。

那么如何給λ,C動態(tài)取值呢。方法有兩種：

第一種是預先生成一張素數(shù)表，讓λ,C在這張表中循環(huán)取值，這種方式λ,C之間沒有規(guī)律性(素數(shù)性質(zhì))，但周期性的大小就取決于這張素數(shù)表的大小，通常而言不會有太多組變化，預生成的表最多也就是幾百個。

第二種方式就是λ,C也動態(tài)計算得出。這樣做其實問題就回到最初的原點，如何使用代碼動態(tài)生成隨機數(shù)然后盡量讓這些數(shù)字的規(guī)律性與周期性盡量低。通過上面的分析已經(jīng)知道，如果λ,C也使用代碼生成的話，在周期性上比方法一有更大的優(yōu)勢(選取較好的λ,C可以在1024*512區(qū)間內(nèi)就有幾十萬種組合，參考圖四)，但規(guī)律性上沒有方法一好。

無論是采用方法一還是方法二，本質(zhì)上都是在混用多個(有限個)線性同余公式的結(jié)果，所以一定還是會有周期性與規(guī)律性的問題。方法一優(yōu)勢在于規(guī)律性非常低，但素數(shù)表的大小決定了周期性大小，通常做不到太多變化，而且占用內(nèi)存。方法二λ,C組合非常多，不需要額外內(nèi)存，但要額外計算，并且這些λ,C是會有一定的規(guī)律性的，優(yōu)勢是周期性非常長，但規(guī)律性上沒有方法一好的。

其實對于游戲邏輯而言，采用固定λ,C的加和線性同模產(chǎn)生的隨機數(shù)已經(jīng)足夠了，效率還會比較高。但如果想做一個質(zhì)量很高的隨機數(shù)生成器，個人建議是采用方法一，然后預先打出一萬以內(nèi)的素數(shù)作為λ,C組合使用，這樣的λ,C組合已經(jīng)有上百萬種了，混用一百萬個加和版本的線性同余算法來生成隨機數(shù)的話，規(guī)律性與隨機性方面應(yīng)該都能滿足計算機領(lǐng)域的使用了。

最后有幾點值得注意的是：

一、計算時使用int或int64，有符號或無符號，對于隨機數(shù)的生成都會有很大影響，計算時要注意

二、如果λ,C 較小而M 非常大，在初期會出現(xiàn)連續(xù)的遞增情況，這三個參數(shù)的選取要注意。

總結(jié)

以上是生活随笔為你收集整理的在计算机上采用线性同余法,随机数生成算法 —— 线性同余法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。