生成方法
一般地,僞随機數的生成方法主要有以下3種:
(1) 直接法(Direct Method),根據分布函數的物理意義生成。缺點是僅适用于某些具有特殊分布的随機數,如二項式分布、泊松分布。
(2) 逆轉法(Inversion Method),假設U服從[0,1]區間上的均勻分布,令X=F-1(U),則X的累計分布函數(CDF)為F。該方法原理簡單、編程方便、适用性廣。
(3)接受拒絕法(Acceptance-Rejection Method):假設希望生成的随機數的概率密度函數(PDF)為f,則首先找到一個PDF為g的随機數發生器與常數c,使得f(x)≤cg(x),然後根據接收拒絕算法求解。由于算法平均運算c次才能得到一個希望生成的随機數,因此c的取值必須盡可能小。顯然,該算法的缺點是較難确定g與c。
因此,僞随機數生成器(PRNG)一般采用逆轉法,其基礎是均勻分布,均勻分布PRNG的優劣決定了整個随機數體系的優劣。下文研究均勻分布的PRNG。
程序實例
C語言程序例
下面看這樣一個C程序://rand01.c
#include
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;
movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);
RAND_SEED=temp;
}
main()
{
unsigned int i,n;
random_start();
for(i=0;i<10;i++)
printf("%ut",random());
printf("n");
}這個程序(rand01.c)完整地闡述了随機數産生的過程:
首先,主程序調用random_start()方法,random_start()方法中的這一句我很感興趣:
movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);
這個函數用來移動内存數據,其中FP_SEG(far pointer to segment)是取temp數組段地址的函數,FP_OFF(far pointer to offset)是取temp數組相對地址的函數,movedata函數的作用是把位于0040:006CH存儲單元中的雙字放到數組temp的聲明的兩個存儲單元中。這樣可以通過temp數組把0040:006CH處的一個16位的數送給RAND_SEED。
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);
正是把TIMER_LOW和TIMER_HIGH兩個16位二進制數放進temp數組,再送往RAND_SEED,從而獲得了“随機種子”。
可以确定的一點是,随機種子來自系統時鐘,确切地說,是來自計算機主闆上的定時/計數器在内存中的記數值。這樣,我們總結一下前面的分析,并讨論一下這些結論在程序中的應用:
1.随機數是由随機種子根據一定的計算方法計算出來的數值。所以,隻要計算方法一定,随機種子一定,那麼産生的随機數就不會變。
C++程序例
僞随機數理論推導
僞随機數理論推導
看下面這個C++程序:
//rand02.cpp
#include
using namespace std;
int main()
{
unsigned int seed=5;
srand(seed);
unsigned int r=rand();
cout<<"r = "<
return 0;
}在相同的平台環境下,編譯生成exe後,每次運行它,顯示的随機數都是一樣的。這是因為在相同的編譯平台環境下,由随機種子生成随機數的計算方法都是一樣的,再加上随機種子一樣,所以産生的随機數就是一樣的。
2.隻要用戶或第三方不設置随機種子,那麼在默認情況下随機種子來自系統時鐘(即定時/計數器的值)
C++程序例2
看下面這個C++程序:
//rand03.cpp
#include
#include
using namespace std;
int main()
{
srand((unsigned)time(NULL));
unsigned int r=rand();
cout<<"r = "<
return 0;
}
這裡用戶和其他程序沒有設定随機種子,則使用系統定時/計數器的值做為随機種子,所以,在相同的平台環境下,編譯生成exe後,每次運行它,顯示的随機數會是僞随機數,即每次運行顯示的結果會有不同。
3.建議:如果想在一個程序中生成随機數序列,需要至多在生成随機數之前設置一次随機種子。
生成一個随機字符串
看下面這個用來生成一個随機字符串的C++程序:(原來的程序我編譯不了,就改了改,加了一些頭文件)(我不是上面那個括号裡的人。我又對源程序進行了一下簡化,可以實現相同的功能)
#include
#include
#include
#define n 20
using namespace std;
int main()
{
srand (time(0));
for (int i=0;i
cout<
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的差異性尤為嚴重。