Posted on 2008-04-15 14:01
Fox 閱讀(4351)
評論(3) 編輯 收藏 引用 所屬分類:
G游戲編程
Author: Fox
John von Neumann說：Any one who considers arithmetical methods of producing random digits is , of course, in a state of sin.
所以，在討論算法實現隨機數的時候，總是說“偽隨機數”。
現在，應用最廣的隨機數生成算法是由Derrick Henry Lehmer1951年給出的線性同余法：
????????????? Xn+1 = ( aXn + c ) mod m,? n>=0.
在上一篇偽隨機數的論述中，并沒有給出X0, a, c, m的取值規則，只是給出了ANSI C和Microsoft Visual C++的實現。
在這兒我們可以自己先思考一下，我們期望從上式中得到的隨機數應該滿足：
1) 上式的輸出足夠隨機，這是最基本的要求；
2) 上式給出盡量多的輸出，越接近m個越好（不可能超過m），即周期盡量長，最好為m，這樣才能保證上式滿足均勻分布（m個數在周期m中各出現一次m個數出現的概率相等）；
3) 上式的生成速度足夠快。
最容易想到的，m的取值為計算機字大?。ㄈ?^32或2^64）。
但是這兒有個很嚴重的問題：Xn低位的隨機性很弱。原因如下：
令d|m, 且
????????????? Yn = Xn mod d
則
????????????? Yn+1 = ( ( aXn + c ) mod m ) mod d
????????????????????? = ( aYn + c ) mod d
上述表達式的意義即：Yn為Xn低k位（d=2^k），這樣的Yn序列形成周期為d甚至更短的同余序列。舉例說明：d為2^1時，Yn為Xn的最低位（可假定為1或0），若Yn+1 != Yn，則Yn+2 == Yn必定成立，僅當a、c皆為奇數時Yn、Yn+1將0、1交替，否則，為常數（0或1）。
暫時拋開隨機性不管，先找到周期為m的隨機序列中的取值規則。
Donald Knuth在The Art of Computer Programming, Volume 2: Seminumerical Algorithms中的3.2.1.2節對m, a, c和X0取值規則的表述：
1) gcd(c, m) = 1. 即c, m互素，再白一點，c, m除1之外沒有其他公因子；
2) 任給質數p, p|m ==> p|(a-1). 即m%p==0，則(a-1)%p==0。
3) 4|m ==> 4|(a-1). 即m%4==0，則(a-1)%4==0。
這個證明過程對于我這樣的數論基礎不是很扎實的搞應用技術的人來說有點難以理解了。有興趣的話，還是去看3.2.1.2的證明吧:-)。
上面的規則告訴我們，滿足了上述規則后，可以保證序列周期為m。對于前面提到的關于隨機性的問題，既然Xn低位的隨機性比較弱，可以只取Xn的高位作為輸出。高位的隨機性和統計意義由a, c確定，其取值涉及統計檢驗，具體的也還是看3.3吧。
這篇文章解決了具有統計意義的隨機數的部分理論問題。
PS: 之前曾經BS過Windows Live Writer，當時覺得Writer編輯功能太少，不能直接設定鏈接文字的字體顏色，知道CSS可以設定之后，又覺得Word 2007編輯的Blog轉成html之后太大，而且也知道Word 2007上面是可以設置鏈接的target為_blank的?，F在發現Writer還是很不錯的了，原來是可以設定格式的，也可以直接編輯html，而且可以Web預覽，鏈接還可以加入到鏈接詞匯表，挺方便的。
越來越發現Wikipedia是個和Google一樣的好東西！