[RAND] 簡介－Edison.X. Blog

前言

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 一些問題。

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

R_n = ( R_n-1 - R_n-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 所產生，但這結果常讓人高度不滿意。較好的取樣結果「可能」長這樣

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

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