Author: Fox

John von Neumann說：Any one who considers arithmetical methods of producing random digits is , of course, in a state of sin.

所以，在討論算法實現(xiàn)隨機數(shù)的時候，總是說“偽隨機數(shù)”。

現(xiàn)在，應用最廣的隨機數(shù)生成算法是由Derrick Henry Lehmer1951年給出的線性同余法：

????????????? Xn+1 = ( aXn + c ) mod m,? n>=0.

在上一篇偽隨機數(shù)的論述中，并沒有給出X0, a, c, m的取值規(guī)則，只是給出了ANSI C和Microsoft Visual C++的實現(xiàn)。

在這兒我們可以自己先思考一下，我們期望從上式中得到的隨機數(shù)應該滿足：

1) 上式的輸出足夠隨機，這是最基本的要求；

2) 上式給出盡量多的輸出，越接近m個越好（不可能超過m），即周期盡量長，最好為m，這樣才能保證上式滿足均勻分布（m個數(shù)在周期m中各出現(xiàn)一次m個數(shù)出現(xiàn)的概率相等）；

3) 上式的生成速度足夠快。

最容易想到的，m的取值為計算機字大小（如2^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皆為奇數(shù)時Yn、Yn+1將0、1交替，否則，為常數(shù)（0或1）。

暫時拋開隨機性不管，先找到周期為m的隨機序列中的取值規(guī)則。

Donald Knuth在The Art of Computer Programming, Volume 2: Seminumerical Algorithms中的3.2.1.2節(jié)對m, a, c和X0取值規(guī)則的表述：

1) gcd(c, m) = 1. 即c, m互素，再白一點，c, m除1之外沒有其他公因子；

2) 任給質數(shù)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。

這個證明過程對于我這樣的數(shù)論基礎不是很扎實的搞應用技術的人來說有點難以理解了。有興趣的話，還是去看3.2.1.2的證明吧:-)。

上面的規(guī)則告訴我們，滿足了上述規(guī)則后，可以保證序列周期為m。對于前面提到的關于隨機性的問題，既然Xn低位的隨機性比較弱，可以只取Xn的高位作為輸出。高位的隨機性和統(tǒng)計意義由a, c確定，其取值涉及統(tǒng)計檢驗，具體的也還是看3.3吧。

這篇文章解決了具有統(tǒng)計意義的隨機數(shù)的部分理論問題。

PS: 之前曾經(jīng)BS過Windows Live Writer，當時覺得Writer編輯功能太少，不能直接設定鏈接文字的字體顏色，知道CSS可以設定之后，又覺得Word 2007編輯的Blog轉成html之后太大，而且也知道Word 2007上面是可以設置鏈接的target為_blank的。現(xiàn)在發(fā)現(xiàn)Writer還是很不錯的了，原來是可以設定格式的，也可以直接編輯html，而且可以Web預覽，鏈接還可以加入到鏈接詞匯表，挺方便的。

越來越發(fā)現(xiàn)Wikipedia是個和Google一樣的好東西！