偽隨機數(shù)算法(一)

戰(zhàn)神之家 2018-01-31

展開全文

　　偽隨機數(shù)概念在我大學(xué)一年級接觸C語言基礎(chǔ)的時候就聽說過,，并熟練掌握C語言中rand()函數(shù)的使用方法。不過,，當時我對偽隨機數(shù)的認識基本也就停留在百度百科那種小白水平,，最多就知道老師說我們用的隨機數(shù)是假的，是通過某種算法實現(xiàn)的,。最近學(xué)習(xí)計算物理學(xué)講到Monte Carlo方法時,，通過課本和互聯(lián)網(wǎng)才算真正意義上理解了什么是偽隨機數(shù)。借此文好好總結(jié)一下吧,！

一,、隨機數(shù)的分類

　　在計算物理學(xué)中，隨機數(shù)被準確地分成了三類：真隨機數(shù),、準隨機數(shù),、偽隨機數(shù)。那么這三種的區(qū)別是什么呢,？拷貝一段書上的定義（我覺得寫的挺好的⊙﹏⊙,，其實是懶得想別的表述方式）：

　　1）真隨機數(shù)：產(chǎn)生的數(shù)不可預(yù)計，也不可能重復(fù)產(chǎn)生兩個相同的真隨機數(shù)序列,。真隨機數(shù)只能通過某些隨機的物理過程來產(chǎn)生,，如放射性衰變、電子設(shè)備的熱噪聲等,。

　　2）準隨機數(shù)：其隨機數(shù)序列不具備隨機性質(zhì),，僅僅是用它來處理問題能夠得到正確的結(jié)果,。（老實說，準隨機數(shù)我目前也沒準確理解,，讀者有好的例子請@我）

　　3）偽隨機數(shù)：通過某種數(shù)學(xué)公式或者算法產(chǎn)生的數(shù)值序列,。雖然在數(shù)學(xué)意義上偽隨機數(shù)是不隨機的，但是如果能夠通過統(tǒng)計檢驗,，可以當成真隨機數(shù)使用,。

二、偽隨機數(shù)算法

　　偽隨機數(shù)產(chǎn)生的方法有個逼格挺高的名字---偽隨機數(shù)發(fā)生器,。偽隨機數(shù)產(chǎn)生器中最最最基礎(chǔ)的思想是均勻分布(當然這不是唯一的思路),。一般來說，只敢說"一般來說",，因為我也不敢百分百肯定,，如今主流的編程語言中使用的隨機數(shù)函數(shù)基本采用這種均勻分布思想，而其中最常用的算法就是"線性同余法"（有著很多的別名,，不過我喜歡用這個名字,，原因你懂的→_→）。不BB別的算法,，直接介紹線性同余法,。

　　1. 什么是線性同余法？

　　對于計算機科學(xué)專業(yè)的學(xué)生來說,，八成會接觸一門課,，叫作《離散數(shù)學(xué)》。里面有一章專門介紹初等數(shù)論,，而線性同余法作為產(chǎn)生均勻型偽隨機數(shù)的算法,，有大概一頁的論述（真是一個悲劇(-_-メ)）。當然,，可能很多人在初中或者之后的數(shù)學(xué)競賽中學(xué)過初等數(shù)論,，線性同余法當然也一定是有過接觸的。

　　線性同余法基于如下線性同余方程組

　　用于產(chǎn)生均勻型偽隨機數(shù)的線性同余產(chǎn)生器（與上面的方程符號沒有對應(yīng)關(guān)系）

　　其中,，a為"乘數(shù)",，b為"增量"，m為"模數(shù)",x0為"種子數(shù)",。

　　如果產(chǎn)生的是區(qū)間實在(0,1)之間的,，則只需要每個數(shù)都除以m即可，即取

　　2. 線性同余法產(chǎn)生均勻型偽隨機數(shù)需要注意什么,？

　　　2.1）種子數(shù)是在計算時隨機給出的,。比如C語言中用srand(time(NULL))函數(shù)進行隨機數(shù)種子初始化。

　　 2.2）決定偽隨機數(shù)質(zhì)量的是其余的三個參數(shù)，即a,b,m決定生成偽隨機數(shù)的質(zhì)量（質(zhì)量指的是偽隨機數(shù)序列的周期性）

　　 2.3）一般b不為0,。如果b為零,，線性同余法變成了乘同余法，也是最常用的均勻型偽隨機數(shù)發(fā)生器,。

　　3. 高性能線性同余法參數(shù)取值要求,？

　　　3.1）一般選取方法：乘數(shù)a滿足a=4p+1；增量b滿足b=2q+1,。其中p,，q為正整數(shù)。 PS:不要問我為什么,，我只是搬運工，沒有深入研究過這個問題,。

　　 3.2）m值得話最好是選擇大的,，因為m值直接影響偽隨機數(shù)序列的周期長短。記得Java中是取得32位2進制數(shù)吧,。

　　 3.3）a和b的值越大,，產(chǎn)生的偽隨機數(shù)越均勻

　　　3.4）a和m如果互質(zhì)，產(chǎn)生隨機數(shù)效果比不互質(zhì)好,。

三,、偽隨機數(shù)代碼實現(xiàn)

　　本文采用Java代碼實現(xiàn)偽隨機數(shù)算法（當然不是調(diào)用Java庫函數(shù)，也不是抄它的代碼）,。產(chǎn)生序列的均勻性可以通過Matlab或者導(dǎo)入Excel作圖直觀檢驗,。

 1 package monteCarlo;
 2 
 3 public class MonteCarlo {
 4     private static final int MAXN = 1 << 20;
 5     private int[] x;
 6     
 7     public MonteCarlo() {
 8         x = new int[MAXN];
 9     }
10     
11     public void rand() {
12         x[0] = (int)(Math.random()*100 + 1);  // 隨機種子(可以用日期產(chǎn)生)
13         /* 保證m與a互質(zhì) */
14         int m = MAXN;  
15         int a = 9;  // a = 4p + 1
16         int b = 7;  // b = 2q + 1
17 
18         System.out.println(x[0]);
19         /* 取前1w個數(shù)*/
20         for(int i = 1; i < 10000; ++i) {
21             x[i] = ( a * x[i-1] + b ) % m;
22             System.out.println(x[i]);
23         }    
24     }
25     
26     public static void main(String[] args) {
27         MonteCarlo mc = new MonteCarlo();
28         mc.rand();
29     }
30 }