Author: Fox

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

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

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

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

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

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

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

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

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

最容易想到的，m的取值為計(jì)算機(jī)字大小（如2^32或2^64）。

但是這兒有個(gè)很嚴(yán)重的問題：Xn低位的隨機(jī)性很弱。原因如下：

令d|m, 且

????????????? Yn = Xn mod d

則

????????????? Yn+1 = ( ( aXn + c ) mod m ) mod d

????????????????????? = ( aYn + c ) mod d

上述表達(dá)式的意義即：Yn為Xn低k位（d=2^k），這樣的Yn序列形成周期為d甚至更短的同余序列。舉例說明：d為2^1時(shí)，Yn為Xn的最低位（可假定為1或0），若Yn+1 != Yn，則Yn+2 == Yn必定成立，僅當(dāng)a、c皆為奇數(shù)時(shí)Yn、Yn+1將0、1交替，否則，為常數(shù)（0或1）。

暫時(shí)拋開隨機(jī)性不管，先找到周期為m的隨機(jī)序列中的取值規(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互素，再白一點(diǎn)，c, m除1之外沒有其他公因子；

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

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

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

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

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

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