這篇筆者認為寫得沒系統,對初學者而言不夠清楚 ,有些地方也寫錯,有興趣可參考另一篇 

[亂數] <細說> C/C++ 亂數基本使用與常見問題

 ,本文予以關閉。


 前言:

1. 亂數部份吾人有所「輕微長進」,有空時將再為此文進行修改,以期本文更加完整。錯誤部份、不佳部份並不予以刪除因這些極有可能為他人會犯之點。吾人亂數部份受Jacob Lee 指導甚多,在此特別感謝!

2. 亂數的分佈情形不只一種,這裡探討的是「均勻分佈」 (其它分佈有機會再補上)。

3. 待補上 Knuth-shfftle

----------------- 分隔線 ----------------- 分隔線 ----------------- 分隔線 -----------------

 1. 初始化

C / C++ 底上,若要產生一亂數會用到的表頭檔如下:

#include <stdlib.h> // srand  與 rand, C++ 為 cstdlib
#include <time.h>  // time(), C++ 為 ctime

在初始化時, 必須先設定亂數種子,否則每次跑出來的亂數都一樣,且需注意件事,以 time 為亂數種子時,仍每秒更新一次,故 srand 事實上沒必要(也不能)放在 loop 裡面一直執行。設定亂數種子方法如下所示:

srand(time(NULL));

另外,整個程式中,亂數種子只需設一次便可,所以 srand 沒必要放在回圈裡面,那只會使執行速度變慢。C 裡之 rand() 使用的是 uniform distribution。其餘的 bernoulli、binomial、... etc,去 MSDN 下載 Visual C++ 2008 Feature Pack Release,裡面有進行支援。

2. 取得亂數

接著呼叫 rand() 便可產生隨機亂數,隨機亂數的範圍為 0 ~RAND_MAX,RAND_MAX 為一 macro,在我的電腦與Complier 底下是被定義為 32767。以下例子便示範跑 100 遍亂數。

for(int i=0; i<100; i++) rand();

3. 設亂數範圍 (1~6之整數)

像是擲骯子,它的點數就只有 1 ~ 6 點,我們可以這麼做

rand()%6 + 1; // worst

rand() %6 的結果一定是落於 0~5 間之整數,把這結果加1後,便成為 1~6 之間的整數。

[Lemma]

這種方式重覆機率很高,對於「均勻」條件差了點,使用下面方式較為佳: (int) ( (6-1) * (double)rand()/RAND_MAX )+1;

4. 設亂數範圍 ([-2,2] 之整數)

這裡和上面差不多,以整數來看,-2~+2 中間有5個整數 (-2,-1,0,1,2),於是我們可以這麼做

rand()%5-2;

rand()%5 之結果必落於 0~4 之間,把這結果減2後,便成為 -2~+2 之整數。於是我們可得到一歸納,要取得 low 與 up 之間之整數亂數為

rand()%(up-low+1) + low

[Lemma]

為符合均勻性,較常使用這種方式做: (up-low) * (double)rand()/RAND_MAX + low;  此法不論是整數或浮點數均適用!若浮點數要考慮是小數後幾位,可再用此法進行四捨五入等方式做調整。

5. 設亂數範圍 ( [-1,1] 之浮點數 )

(5.1) 設 [0,1] 之浮點數亂數

剛有介紹過, 使用 rand 時,其最大值為 RAND_MAX, 於是若要設 0~1 亂數便這麼做

(double)rand()/RAND_MAX;

加上 double 是為了強制轉成浮點數,避免產生相除等於零之情形。

[Lemma]

加註區間性問題 ( 感謝 Jacob Lee 提醒 )

產生 [0,1) 之浮點數:(double)rand() / (RAND_MAX+1);
產生 [0,1] 之浮點數:(double)rand() / RAND_MAX;
產生 (0,1) 之浮點數:(double) (rand()+1) / (RAND_MAX +2); // 思考是否有其他問題存在中
產生 (0,1] 之浮點數:(double) (rand()+1) / (RAND_MAX +1); // 思考是否有其他問題存在中

(5.2) 產生 [-1,+1] 之浮點亂數

這種做法起碼三種, 我只說較簡單的方法。雖產生 [0,1] , 但實際上要產生的是 [-1,1] , 由於間隔為2,所以把分子乘以二倍再除上 RAND_MAX。

(double)rand()*2 / RAND_MAX + (-1) ;

於是我們產生了一通式:[up, down] ---> (double)rand()*(up-down) / RAND_MAX + down;

6. 取得 N 個 1~X不重覆亂數, 其中 X>N

(6.1) 撲克洗牌法

建立 X 張撲克牌,點數為 1~X ,隨機抽二張牌交法(抽的次數有人說 X/2 次,也有人說抽 X 次),最後再從牌堆裡面拿出 N 張出來。

int i, t1, t2, Array[X],tmp; // x 張 poker
for(i=0; i<N; i++) Array[i] = i+1; // 產生 1~N 之點數
for(i=0; i<X; i++){ // 從牌堆抽二張交換
     t1 = rand() % X, t2 = rand() % X;
     tmp = Array[t1];
     Array[t1] = Array[t2];
     Array[2=t2] = tmp;
} // 洗牌完畢

// 發出前 N 張
for(i=0; i<N; i++) // printf("%d\n", Array[i]);

(6.2) 改良式 poker

上一個例子我們是隨意抽二張, 但有些人認為要每一張都抽過, 於是就變成, 第一張先選定, 抽一張跟第一張換; 第二張再選定, 抽一張和第二張換... 第 X 張選定, 抽一張與第 X 張換。

int i, pos ,tmp, array[i];
for(i=0; i<X; i++) array[i] = i+1; // 產生點數
for(i=0; i<X; i++) { // 依序交換每一張
     pos = rand()%X;
     tmp = array[i];
     array[i] = array [pos];
     array[pos] = tmp;
}

(6.3) Kunth-shfftle (待補)

7. 亂數所需範圍超過 RAND_MAX

 Y=AX+B,  現在假設要產生 [0,100000] 亂數, 比我手邊的 32767 還大, 要怎麼產生 ?

32767 * 2 = 65534 < 100000
32767 * 3 = 98301 < 100000
32767 * 4 = 131068 > 10000

於是我將所產生出之亂數乘上 4 倍 再 mod 10000。

rand()*4%10000;

有時這樣便可滿足需求,有時則否。不能滿足的原因大多如下

rand() = 1 ->  1*4 % 100000 = 4
rand() = 2 ->  2*4 % 100000 = 4

沒錯, 這樣下去產生的亂數永遠都是 4 的倍數,  可參考以下之解法

(rand()*4 % 100000 + rand()%4) % 100000;

我以前是這麼做,但說真的連我自己都覺得麻煩、很糟。

---------- 分隔線 ---------- 分隔線---------- 分隔線---------- 分隔線 -------

另可考慮第二種做法:

rand() 範圍為 0~ RAND_MAX = 0~32767,使用了 15 bits;於是可考慮:

int rnd = rand() | (rand() << 15) ;

這樣便生成了 30 bits 之亂數,範圍便展開成了 0~ 2^30 - 1 = 1,073,741,824 (約10億, 10^9),到時再進行 mod 運算,但這種方式絕不可能會使得 rnd=0  ( 連續取二個 rand() 若數值相同,那這個產生器是失敗的!)

類似要擴展的方式也類似,但聲明,這些方式都有著「不均勻」問題,同時有些數字可能都不會出現的問題

int rand31(){
    // RAND31_MAX = 2147483647
    return ( (rand() << 16) | (rand() << 1) | (rand() & 1) );
}

unsigned int rand32() {
    // RAND32_MAX = 4294967295
    return ( (rand() << 17) | (rand() << 2) | (rand() & 3) );
}

要徹底解決這個問題, 我想除了找 lib, 換 complier, 再來就是自己寫亂數產生器了。

8. 其他函式庫

(8.1) c++ STL - random_shuffle

使用 random_shuffle 去洗

const int N = 8;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N);

(8.2) 網路提供之函式庫與說明

Mersenne Twister : Wiki C/C++ download

Monte Carlo methods in Wiki

Visual C++ 2008 Feature Pack Release這個強烈建議一定要去載來安裝!裡面加強了許多功能,其中亂數也加強了很多 (待吾人研究後慢慢發心得)

 

---------- 分隔線 ---------- 分隔線---------- 分隔線---------- 分隔線 -------

[亂數可研究議題、文獻甚多,若有興趣可再深入研究。]

 

arrow
arrow
    全站熱搜

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