前言

1. 這系列文章主要在探討亂數問題,我認為任何 coder 即使不知道如何寫出一份亂數產生器,但應必須知道亂數之原理及其使用之注意事項。

2. 此系列文章所參考之資料甚多,也承蒙各方好手之指導,由於內容真的有點多,若無心想一一探討,可參考 目錄 之部份,選擇自己所需之部份加以進修即可。

3. 部份綴詞沒使用得很好,主因乃試著將閱讀過的英文文獻,以中文去解釋它,部份單字我仍會保留原文,若覺語意有誤,請不吝指正。

4. 撰文過程中,若出現 mod 或 MOD ,代表是取模之意,以 a mod b 為例,就是 a 除以 b 取餘數。如 101 mod 3 = 2,因 101 除以 3 ,商為 33,餘數為 2;若出現 PRNG,指的是 Pseduo Random Number Generate,虛擬亂數產生器。

5. 本系列探討之文章,主要以均勻分佈之亂數為主。

6. The art of computer programming, Vol2 Chapter 3 , by Kunth,這章可做為相當之參考。


   亂數產生器(Random Number Generate, RNG)

 

目前電腦所產生之亂數,都是用「虛擬化」方式隨機產生,意思是沒辦法產生「真正」的亂數產生器。因目前亂數產生器,乃利用人工已知之序列原理 (簡單、常見的是一組公式),去虛擬製造出一系列之數值,而這類之亂數產生器,都稱作是虛擬亂數產生(Pseduo Random Number Generate, PRNG)。PRNG 通常必須滿足以下幾個性質

1. Quality (品質) : 必須可滿足統計測試之適用度,且在亂數重覆時,必須為長週期。

2. Efficiently (效率) : 必須可快速產生一個亂數,產生亂數運算過程中,盡可能降低所需之空間。

3. Repeatability (重複性) :此產生器可進行攜帶(seedable) 到別台電腦,且可重覆使用。

4. Portability (可移植) : 可移植至在不同系統中,同時相同之產生器會有相同之結果。

5. Simplicity (簡易性) :產生器必須便於使用與實現。

 

 


費式亂數產生器 (Fibonacci generator)

 

聲明,以下說明不是真正的 Fibonacci generator,只是引出 PRNG 一些問題。

經過上面解釋後,來看看下面這個東西加深印象。假設一個亂數產生器,它的公式長這樣

Rn = ( Rn-1 - Rn-2) mod M  (for n is integer and n >= 2)

也就是說,這個亂數是前二個亂數相減的結果。所有亂數產生器,一開始都必須決定初值,以上述的 Rn 而言,就必須先決定 R0 與 R1 為多少。這也是為什麼一開始一般在調用 rand 時,要先用 srand 的原因。

假設產生器欲產生 0~ 32767 之亂數,以 C 語言撰之,程式碼大略如下  

static int seed1, seed2;
const static int M = 32768;
void set_seed(int n1, int n2)
{
    seed1=n1;
    seed2=n2;
}

int fib_seed()
{
    int result = (seed2 - seed1) % M;
    seed1 = seed2;
    seed2 = result;
    return result;
}

 

其中 set_seed(int n1, int n2) 便是去設其亂數種子 seed1, seed2。馬上寫個程式來測試看看

 

int main()
{
    int i=0;
    set_seed(2, 10);
    for(i=0; i!=20; ++i) printf("%d ", fib_seed());
    return 0;
}

結果

2 10 8 -2 -10 -8 2 10 8 -2 -10 -8 2 10 8 -2 -10 -8 2 10 8 -2

這個結果可以發現,有負號 (事實上有另一個問題在下面說明),這和一開始的前提:產生  0~32767 之亂數不符合,於是小改成以下寫法

int fib_seed()
{
    int result = (seed2 - seed1) % M;
    if(result<0) result=-result;
    seed2 = seed1;
    seed1 = result;
    return result;
}

 

這次跑出來的結果是

2 10 8 2 6 4 2 2 0 2 2 0 2 2 0 2 2 0 2 2 0 2

的確都在範圍內了,但這樣觀查可發現,這種寫法真的也非常不好!明明是要產生 0~32767 之亂數,但取了 7 次便開始重覆,從頭到尾就只有 0 2 4 6 8 這五個數字在跑而已。

再回到前面所提到,PRNG 必須滿足五個特性:

1. Quality (品質) : 此 fib_gen 於短週期便開始重覆,失敗。
2. Efficiently (效率) : 確實效率非常快,它只有用到簡單的 assignment、adder ,效率極高。
3. Repeatability (重複性) :的確也可拿到其它電腦使用。
4. Portability (可移植) : 於不同之系統「可能」產生出來的結果會不同,原因在於 正數 mod 負數,出來的結果並不相同,這部份是看機器的結果。
5. Simplicity (簡易性) : 這應是我看過最簡單的亂數產生器。

這隻亂數產生器對於2、3、5 符合度極高,但對於品質與可移植性卻很差!所以上面的 PRNG 不能使用!

要再改嗎?

這隻 Fibonacci generator 事實上於 1950 年代非常受歡迎,也是基於 Fibonacci sequence 所產生,但這結果常讓人高度不滿意。較好的取樣結果「可能」長這樣

Rn+1 = ( Rn-97 - Rn-33) mod M  ,

這種方式在 1960 年代之 super computer 非常受歡迎,本文僅以此 PRNG 突顯出亂數產生器之一些問題,故不續談此 Fibonacci generator。

, ,

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()