-
偽隨機數
鎖定
- 中文名
- 偽隨機數
- 外文名
- Pseudo-random Number
- 方 法
- 直接法，逆轉法
- 應 用
- 程序語言
- 性 質
- 名詞
偽隨機數生成方法
一般地，偽隨機數的生成方法主要有以下3種：
（1） 直接法（Direct Method），根據分佈函數的物理意義生成。缺點是僅適用於某些具有特殊分佈的隨機數，如二項式分佈、泊松分佈。
（2） 逆轉法（Inversion Method），假設U服從[0，1]區間上的均勻分佈，令X=F-1（U），則X的累計分佈函數（CDF）為F。該方法原理簡單、編程方便、適用性廣。
偽隨機數發生器
因此，偽隨機數生成器（PRNG）一般採用逆轉法，其基礎是均勻分佈，均勻分佈PRNG的優劣決定了整個隨機數體系的優劣[7]。下文研究均勻分佈的PRNG。
偽隨機數程序實例
C語言程序例
偽隨機數
//rand01.c
#include <stdlib.h>
static unsigned int RAND_SEED;
unsigned int random(void)
{
RAND_SEED=(RAND_SEED*123+59)%65536;
return(RAND_SEED);
}
void random_start(void)
{
int temp[2];
movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);
RAND_SEED=temp[0];
}
main()
{
unsigned int i,n;
random_start();
for(i=0;i<10;i++)
printf("%u\t",random());
printf("\n");
}
這個程序（rand01.c）完整地闡述了隨機數產生的過程：
首先，主程序調用random_start方法，random_start方法
movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);
偽隨機數理論推導
random用來根據隨機種子RAND_SEED的值計算得出隨機數，其中這一句：
RAND_SEED=(RAND_SEED*123+59)%65536;
是用來計算隨機數的方法，隨機數的計算方法在不同的計算機中是不同的，即使在相同的計算機中安裝的不同的操作系統中也是不同的。linux和windows下分別試過，相同的隨機種子在這兩種操作系統中生成的隨機數是不同的，這説明它們的計算方法不同。
明白隨機種子是從哪兒獲得的，而且知道隨機數是怎樣通過隨機種子計算出來的了。那麼，隨機種子為什麼要在內存的0040:006CH處取。0040:006CH處存放的是什麼。
學過《計算機組成原理與接口技術》這門課的人可能會記得在編制ROM BIOS時鐘中斷服務程序時會用到Intel 8253定時/計數器，它與Intel 8259中斷芯片的通信使得中斷服務程序得以運轉，主板每秒產生的18.2次中斷正是處理器根據定時/計數器值控制中斷芯片產生的。在計算機的主機板上都會有這樣一個定時/計數器用來計算當前系統時間，每過一個時鐘信號週期都會使計數器加一，而這個計數器的值存放在哪兒呢。沒錯，就在內存的0040:006CH處，其實這一段內存空間是這樣定義的：
TIMER_LOW DW ? ；地址為 0040:006CH
TIMER_HIGH DW ? ；地址為 0040:006EH
TIMER_OFT DB ? ；地址為 0040:0070H
時鐘中斷服務程序中，每當TIMER_LOW轉滿時，此時，記數器也會轉滿，記數器的值歸零，即TIMER_LOW處的16位二進制歸零，而TIMER_HIGH加一。rand01.c中的
movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);
1.隨機數是由隨機種子根據一定的計算方法計算出來的數值。所以，只要計算方法一定，隨機種子一定，那麼產生的隨機數就不會變。
C++程序例
偽隨機數理論推導
//rand02.cpp
#include <iostream>
using namespace std;
int main()
{
unsigned int seed=5;
srand(seed);
unsigned int r=rand();
cout<<"r = "<<r<<endl; //根據C++ 98標準,可以不用return語句來結束main函數
return 0;
}
在相同的平台環境下，編譯生成exe後，每次運行它，顯示的隨機數都是一樣的。這是因為在相同的編譯平台環境下，由隨機種子生成隨機數的計算方法都是一樣的，再加上隨機種子一樣，所以產生的隨機數就是一樣的。
2.只要用户或第三方不設置隨機種子，那麼在默認情況下隨機種子來自系統時鐘（即定時/計數器的值）
C++程序例2
看下面這個C++程序：
//rand03.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
srand((unsigned)time(NULL));
unsigned int r=rand();
cout<<"r = "<<r<<endl; //根據C++ 98標準,可以不用return語句來結束main函數
return 0;
}
這裏用户和其他程序沒有設定隨機種子，則使用系統定時/計數器的值做為隨機種子，所以，在相同的平台環境下，編譯生成exe後，每次運行它，顯示的隨機數會是偽隨機數，即每次運行顯示的結果會有不同。
3.建議：如果想在一個程序中生成隨機數序列，需要至多在生成隨機數之前設置一次隨機種子。
生成一個隨機字符串
看下面這個用來生成一個隨機字符串的C++程序
#include <iostream>
#include <ctime>
#include <cstdlib>
#define n 20
using namespace std;
int main()
{
srand (time(0));
for (int i=0;i<n;++i) cout<<char(rand()%26+97);
cout<<endl;
return 0;
}
偽隨機數發生器
可能會遇到這種情況，在VB中，在使用timer控件編制程序的時候會發現用相同的時間間隔生成的一組隨機數會顯得有規律，而由用户按鍵command事件產生的一組隨機數卻顯得比較隨機，為什麼，根據上面的分析，可以很快想出答案。這是因為timer是由計算機時鐘計數器精確控制時間間隔的控件，時間間隔相同，計數器前後的值之差相同，這樣時鐘取值就是呈線性規律的，所以隨機種子是呈線性規律的，生成的隨機數也是有規律的。而用户按鍵事件產生隨機數確實更呈現隨機性，因為事件是由人按鍵引起的，而人不能保證嚴格的按鍵時間間隔，即使嚴格的去做，也不可能完全精確做到，只要時間間隔相差一微秒，計數器前後的值之差就不相同了，隨機種子的變化就失去了線性規律，那麼生成的隨機數就更沒有規律了，所以這樣生成的一組隨機數更隨機。這像各種晚會的抽獎程序，如果用人來按鍵產生幸運觀眾的話，那就會很好的實現隨機性原則，結果就會更公正。
總結
1.計算機的偽隨機數是由隨機種子根據一定的計算方法計算出來的數值。所以，只要計算方法一定，隨機種子一定，那麼產生的隨機數就是固定的。
2.只要用户或第三方不設置隨機種子，那麼在默認情況下隨機種子來自系統時鐘。
偽隨機數生成器缺點
重複做N=10000次試驗，每次產生S=20與S=100個隨機分佈的樣本，同時採用Kolmogorov- Smirnov假設檢驗（hypothesis test）來確定樣本是否滿足均勻分佈。規定：
① 0假設（null hypothesis）為樣本服從均勻分佈；② 1假設（alternative hypothesis）為樣本不服從均勻分佈。
採用P值（∈[0， 1]）衡量，P值越趨近於0，表示越有理由拒絕0假設，即樣本不服從均勻分佈；P值越趨近於1，表示越有理由接受0假設，即樣本服從均勻分佈。
隨着P值下降，樣本也越來越不服從均勻分佈。實踐中希望P值越大越好。然而統計學的結論顯示，P值一定服從均勻分佈，與N、S大小無關，這表明由於隨機性，總會出現某次抽樣得到的樣本不服從、甚至遠離均勻分佈。另外，樣本大小的不同，造成檢驗標準的不同，直觀上看S=100對應的均勻分佈普遍比S=20對應的更均勻。因此，小樣本情況下均勻分佈PRNG的差異性尤為嚴重。
