Linear congruential generator
中文翻譯為線性同餘法(以下簡稱lcg)
主要是用來產生亂數的一個公式
這公式的內容為
X = (a * X + c) (mod m)
其中 a , c , x都會小於 m 大於零
且 1. c , m 互質
2. a-1會被 m的所有質因數整除
3. 如果 m 被 4 整除 a-1也會被 4 整除
看起來還好對吧
湊完數字之後也能work
跑500次之後把數字列出來看也還蠻分散的
但是!!
個位數不知道位啥有規律= =
當把跑出來的亂數 mod 10之後
再把這些數分成0~9的區間
發現每個區間都是剛剛好50個 =口=|||
先來講一下一開始的做法
由於題目要求是要 0 ~ 100000之間的整數
所以最簡單的想法就是 m = 100000
這樣不用對亂數做任何手腳就會是 0 ~ 100000 之間的數
這樣一來 a 跟 c 也好決定
但是這樣的結果是
我跟保安用的 a c 數字組不同
個位數都出現了一樣的問題 囧rz
留在學校研究了半天也沒搞定
後來是參雜middle-square法來產生亂數
但是這樣跑出來的亂數分布又不夠均勻
後來回家洗完澡之後在網路上查到了一篇論文
內容主要是在討論各統計軟體在產生亂數夠不夠亂
(這時候就慶幸自己是應數系的勉強還看的懂一些XD)
後來看到某個統計軟體是用組合型的 lcg
這邊提一下lcg還有分很多種
像是 c = 0 的分為一種
c 不等於 0 的一種
剛剛講的多個 lcg 合起來的又是一種
最後結果是用
x = 171 * x % 30269
y = 172 * y % 30307
z = 170 * z % 30323
這三組去合成一個 lcg (三組 c 都為 0)
至於數值內容 很可怕 不要問
不是 這三組數字其實是由Wichmann和Hill(1982)提出
這兩個傢伙是誰我也不知道
反正應該是兩個很閒的數學家就是了
可惜的是組合出來跑出的數是0~1之間
還是得對method做點手腳讓回傳值落在0~100000之間
不過跑出來的成果還算令人滿意
也觀察不出有沒有規律(還是其實是我沒看出來=口=)
嘛~就這樣不想改啦> <
沒有留言:
張貼留言