Edison.X. Blog

 
陸陸續續寫了 EA  一、二年，以前亂數引導文回頭看時才發現，怎麼有這麼多細節的錯誤、沒系統。
這篇文章主要引導初學者使用亂數，同時附上常被翻出來討論的議題，C/C++適用，唯以 C 語言撰之。
也由於是引導初學者，所以在某些用詞上會較不正確，

 
在學數值分析時，會講到如何以均勻分佈，轉換到各種分佈裡，常見的大概會有波松分佈、指數分佈、常態分佈。較有名的方式 Miller-Box Transform 是專用在轉常態分佈 ( 因常態分佈是算常出現的機率模型 )。
一些常見的機率分佈亂數，C++ 都已包到 TR1 裡去，有興趣可自行參考。 
這裡提的轉換方式，當然要有一份均勻的亂數產生器 ( 統計用的均勻就夠了，如  rand() )，另外假設讀者也知道該亂數分佈的  機率函式  f(x) 為何，並可用程式語言表達出該 f(x) ，其 f(x) 長得奇型怪狀也沒差，如

亂數有些議題特別拉出來再次討論，不熟的話 可看這篇。
1.  [low, up]
假定產生 [10,20] 之整數亂數，先考慮以下程式碼

1. 基本觀念
線性同餘法基本上只有一個公式，X(n+1) = ( a * X(n) + b ) mod c，
但並非所有 a, b, c 都適用。以 a=5, b=0, c=10 為例，假定 X(0)=3 代入

以下說明之方法，與平方取中法均有相似之處，其重大缺點都一樣，最後容易面臨退化之窘境。
Midproduct Method (中間乘積法)
中間乘積法初始時，亂數種子必須設二個 s1, s2，假設欲生成 0~32767 之亂數 (15 位)，乃是將 s1*s2 後之結果 (30 位數)，取其中間 15 位數 (32 位元可拆成 9 15 8)。 C 語言大致如下所示
#include <stdio.h>
#include <time.h>
int seed1, seed2;
void MidProduct_srand(int s1, int s2)
{
seed1=s1;
seed2=s2;
}
int MidProduct_rand()
{
int ret = ((seed1 * seed2) & 0x007fffff) >> 8;
seed1 = seed2;
seed2 = ret;
return ret;
}
int main()
{
int i=0;
MidProduct_srand((int)time(NULL), (int)time(NULL));
for(i=0; i!=20; ++i) printf("%d ", MidProduct_rand());
return 0;
}

K algorithm ( "Super-random" number generator)
這是由 Kunth 於 The Art Of Programming 裡提出說明，當時 Kunth 試著以此演算法建立較好之 PRNG，也強調讀者不必特別研究它，故這部份沒太大興趣者可跳過，流程大致如下，其中 ** 代表次方，如 3**5 代表 3 的 5 次方。(以下特別注意 K1, K2)
INIT: 給一 10 位數 X ，進行以下步驟
K1. 選擇迭代次數： Y:= X/(10 ** 9)，執行 K2~K13 ，Y+1次。
K2. 選擇隨機步驟： Z:= Y/(10 ** 8) mod 10，步驟轉向  K(3+Z)
K3. 確保 X >= 5* 10**9： 若 X < 5000000000 ， X := X + 5000000000
K4. 平方取中法： X := (X*X / 10 ** 5) mod 10
K5. 進行乘法： X:= 1001001001X
K6. 假(偽)補數： 若 X < 10 ** 8 ， X:= X+9814055677；否則 X:=10 ** 10 - X
K7. 互換二半： X 高5位與 X 低5位 (十進制) 交換，即 X:= (X mod 10 ** 5) + (X / 10 **5)
K8. 進行乘法： 同 K5
K9. 減小數字：將 X 之十進制表示之每個非 0 數字減 1
K10. 9999修改：若 X<100000，X:=X*X + 9999；否則 X:=X-9999
K11. 正規化：此時 X 不能為零，若 X < 10 ** 9 ，X:=10X，重覆此步驟
K12. 修正之平方取中法： X:= ( X*(X-1) / 10 ** 5  ) mod ( 10 ** 10)，即中間十位數取代 X
K13. 重複 ? ：若 Y>0，Y:=Y-1，回到步驟 K2；若 Y=0，其 X 即為隨機值。

Midsquare method(中間平方法 / 平方取中法)
這部份主要參考 The Art Of Computer Programming.
這方法於 1946 年前後，John Von Neumann 建議用這方法生成亂數。辦法是取前面亂數的平方後，再取中間的數字。如生成 10 位數，先前之值為 1234567890，其平方為 1524157875019052100，於是下個亂數便為 1578750190。

前言
1. 這系列文章主要在探討亂數問題，我認為任何 coder 即使不知道如何寫出一份亂數產生器，但應必須知道亂數之原理及其使用之注意事項。
2. 此系列文章所參考之資料甚多，也承蒙各方好手之指導，由於內容真的有點多，若無心想一一探討，可參考 目錄 之部份，選擇自己所需之部份加以進修即可。
3. 部份綴詞沒使用得很好，主因乃試著將閱讀過的英文文獻，以中文去解釋它，部份單字我仍會保留原文，若覺語意有誤，請不吝指正。

x
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
int main()
{
unsigned i;
int head[N]={0}, test[N]={0};
srand(0);
for(i=0; i!=N; ++i) head[i] = rand();
i=0;
while(memcmp(head, test, N*sizeof(int))){
memcpy(test, test+1, (N-1)*sizeof(int));
test[N-1]=rand();
++i;
}
printf("period=%u\n", i);
printf("int_max=%d\n", INT_MAX);
return 0;
}

這篇筆者認為寫得沒系統，對初學者而言不夠清楚 ，有些地方也寫錯，有興趣可參考另一篇 
[亂數] <細說> C/C++ 亂數基本使用與常見問題
 ，本文予以關閉。