2008年6月14日 星期六

亂數產生器

http://4rdp.blogspot.com/2008/06/blog-post_14.html?m=0

想過電腦中亂數產生器如何設計的嗎?

大多數亂數產生器採用線性同餘法設計 (Linear Congruential Generator, LCG),因為方法簡單以及亂數均勻分佈 (Uniform distribution)。

其原理為,
Xn = a Xn-1 + b     將一正整數乘以 a 常數再加上 b 常數,
0<= Xn<M           除 M 取餘數,這個 Xn 可重複代入上式計算下一個亂數。

 
各位可以參考 EXCEL 檔,我選用 a = 49,b = 0,M = 215 = 32768,C 欄位就是亂數,介於零與一之間,從 E、F 欄位可以看出數值分部非常均勻。
另外,從 A 欄位會發現,每 2048 筆資料會重複循環,這裡所舉的例子是方便讀者明瞭原理,商用軟體至少用32 bits,並挑選合適的 a b 值,所以很難發現重複性。

通常均勻分佈的亂數產生器就夠用,不過與統計有關的程式還需要常態分佈 (Normal distribution) 的亂數產生器,那如何設計呢?還記得中央極限定理 (Central limit theorem) 吧!從未知分佈的母群體中抽樣,只要能計算出這群體平均數 μ 以及有限的變異數 σ2,那麼抽出 n 個隨機樣本取平均值,當 n 趨近無窮大,它的平均值抽樣分配將近似於常態分佈。再以 EXCEL 檔內容為例,一般程式計算時間有限不可能無窮計算下去,因此只取連續六筆資料平均再正規化,原均勻分佈的 C 欄位值,經過計算後就成為 H 欄位常態分佈的亂數,請參考 J 欄位的機率分佈。



另外,常態分佈亂數方法二,請參考 http://4rdp.blogspot.com/2008/06/random-variable-of-normal-distribution.html

授權程式人雜誌 2014 五月刊文

8 則留言:

  1. 我所用過的所有 3C 產品的 隨機數,亂數功能,我都認為 不及格。
    原因是,他們都沒有好好的處理 亂數的種子數的問題。
    所以,開機之後的隨機順序,其實是可以預測的。
    有興趣 討論這個問題的話,可以跟我聯絡。

    回覆刪除
  2. 這是當然噢,百分之九十以上的產品都是採LCG 法,甚至 a b 常數還一樣,初值種子從零開始,那就很容易找到規則,所以初值種子可以用時間找一個代入,就比較難猜,謝謝您的補充。

    回覆刪除
  3. 您好~

    我想請問一下是否能向你索取這篇文章內的excel檔呢? 因為最近正在做這方面的網頁,如果可以的話,在這先謝謝你了!

    我的e-mail : Okischung@gmail.com

    ps.順便問一下,如果我做的是網頁的常態亂數的話,請問可行嗎? 謝謝:)

    回覆刪除
  4. Hi Okis,

    其實您已經登入研發養成所的線上論壇,應可直接下載檔案,不過沒關係,檔案我還是再寄送一次。

    關於您的第二個問題,我並不明白。如果您想設計一常態分佈亂數產生器運用於網頁中,這是可行的,比如說用 JavaScript 寫一個函式,然後於主程式呼叫它即可。

    當您設計出來後,不要忘記分享喔!

    Bridan ^_^

    回覆刪除
  5. 你好
    是否可跟你要有關亂數產生器文章中LCG之EXCEL檔參考,謝謝
    ckliao168@gmail.com

    Louis

    回覆刪除
  6. Hi Louis,

    Excel已經重新設定,你可以直接下載。有問題再連絡我。

    回覆刪除
  7. 真的謝謝你,檔案可以下載了

    回覆刪除
  8. Abner123 您好,

    歡迎參閱本文,也歡迎留言討論。

    回覆刪除