偽隨機數生成及在VC++中的實現

　　摘 要 偽隨機數在計算機軟件設計中有很廣泛的用途。本文介紹了基于數學方法的利用計算機產生偽隨機數的一種方法，即線性同余法，任何偽隨機數的產生都是運用遞推的原理來生成的。以及在Visual C++環境中產生偽隨機數的兩個重要函數，rand和srand函數，正確地使用這兩個函數是產生性能良好的偽隨機數的關鍵，最后介紹了利用偽隨機數生成技術在MFC中生成基于C/S模式應用程序的隨機校驗碼以及利用一種軟件工具ImagePassword產生隨機密碼。

　　關鍵詞 偽隨機數生成；線性同余法；Visual C++；隨機校驗碼

　　為追求真正的隨機序列，人們曾采用很多種原始的物理方法用于生成一定范圍內滿足精度（位數）的均勻分布序列，其缺點在于：速度慢、效率低、需占用大量存儲空間且不可重現等。為滿足計算機模擬研究的需求，人們轉而研究用算法生成模擬各種概率分布的偽隨機序列。偽隨機數是指用數學遞推公式所產生的隨機數。從實用的角度看，獲取這種數的最簡單和最自然的方法是利用計算機語言的函數庫提供的隨機數發生器。典型情況下，它會輸出一個均勻分布在0和1區間內的偽隨機變量的值。其中應用的最為廣泛、研究最徹底的一個算法即線性同余法。

　　線性同余法LCG（Linear Congruence Generator）

　　選取足夠大的正整數M和任意自然數n0，a，b，由遞推公式：

clearcase/" target="_blank" >cccccc width="90%" align=center bgColor=#e3e3e3 border=1>

ni+1=（af（ni）+b）mod M i=0，1，…，M-1

　　生成的數值序列稱為是同余序列。當函數f（n）為線性函數時，即得到線性同余序列：

ni+1=（a*ni+b）mod M i=0，1，…，M-1

　　以下是線性同余法生成偽隨機數的偽代碼：

Random（n，m，seed，a，b） { 　r0 = seed； 　for （i = 1；i<=n；i++） 　ri = （a*ri-1 + b） mod m }

　　其中種子參數seed可以任意選擇，常常將它設為計算機當前的日期或者時間；m是一個較大數，可以把它取為2w，w是計算機的字長；a可以是0.01w和0.99w之間的任何整數。

　　應用遞推公式產生均勻分布隨機數時，式中參數n0，a，b，M的選取十分重要。

　　例如，選取M=10，a=b =n0=7，生成的隨機序列為{6，9，0，7，6，9，……}，周期為4。

　　取M=16，a=5，b =3，n0=7，生成的隨機序列為{6，1，8，11，10，5，12，15，14，9，0，3，2，13，4，7，6，1……}，周期為16。

　　取M=8，a=5，b =1，n0=1，生成的隨機序列為{6，7，4，5，2，3，0，1，6，7……}，周期為8。

　　Visual C++中偽隨機數生成機制

　　用VC產生隨機數有兩個函數，分別為rand（void）和srand（seed）。rand()產生的隨機整數是在0~RAND_MAX之間平均分布的，RAND_MAX是一個常量（定義為：#define RAND_MAX 0x7fff）。它是short型數據的最大值，如果要產生一個浮點型的隨機數，可以將rand()/1000.0，這樣就得到一個0~32.767之間平均分布的隨機浮點數。如果要使得范圍大一點，那么可以通過產生幾個隨機數的線性組合來實現任意范圍內的平均分布的隨機數。

　　其用法是先調用srand函數，如

srand( (unsigned)time( NULL ) )

　　這樣可以使得每次產生的隨機數序列不同。如果計算偽隨機序列的初始數值（稱為種子）相同，則計算出來的偽隨機序列就是完全相同的。要解決這個問題，需要在每次產生隨機序列前，先指定不同的種子，這樣計算出來的隨機序列就不會完全相同了。以time函數值（即當前時間）作為種子數，因為兩次調用rand函數的時間通常是不同的，這樣就可以保證隨機性了。也可以使用srand函數來人為指定種子數。
分析以下兩個程序段，

　　程序段1：

//包含頭文件 void main() { 　int count=0; 　for (int i=0;i<10;i++){ 　　srand((unsigned)time(NULL)); 　　count++; 　　cout<<"No"<<count<<"="<<rand()<<" "; 　　if (!(count%5)) cout<<endl; 　} }

　　程序段2：

//包含頭文件 void main() { 　int count=0; 　srand((unsigned)time(NULL)); 　for (int i=0;i<10;i++){ 　　count++; 　　cout<<"No"<<count<<"="<<rand()<<" "; 　　if (!(count%5)) cout<<endl; 　} }

　　程序段1的運行結果為：

No1=9694 No2=9694 No3=9694 No4=9694 No5=9694 No6=9694 No7=9694 No8=9694 No9=9694 No10=9694

　　程序段2的運行結果為：

No1=10351 No2=444 No3=11351 No4=3074 No5=21497 No6=30426 No7=6246 No8=24614 No9=22089 No10=21498

　　可以發現，以上兩個程序段由于隨機數生成時選擇的種子的不同，運行的結果也不一樣。rand()函數返回隨機數序列中的下一個數(實際上是一個偽隨機數序列，序列中的每一個數是由對其前面的數字進行復雜變換得到的)。為了模仿真正的隨機性，首先要調用srand()函數給序列設置一個種子。為了更好地滿足隨機性，使用了時間函數time()，以便取到一個隨時間變化的值，使每次運行rand()函數時從srand()函數所得到的種子值不相同。偽隨機數生成器將作為"種子"的數當作初始整數傳給函數。這粒種子會使這個球（生成偽隨機數）一直滾下去。

　　程序段1中由于將srand（）函數放在循環體內，而程序執行的CPU時間較快，調用time函數獲取的時間精度卻較低（55ms），這樣循環體內每次產生隨機數用到的種子數都是一樣的，因此產生的隨機數也是一樣的。而程序段2中第1次產生的隨機數要用到隨機種子，以后的每次產生隨機數都是利用遞推關系得到的。