Author: Fox
John von Neumann說(shuō)：Any one who considers arithmetical methods of producing random digits is , of course, in a state of sin.
所以，在討論算法實(shí)現(xiàn)隨機(jī)數(shù)的時(shí)候，總是說(shuō)“偽隨機(jī)數(shù)”。
現(xiàn)在，應(yīng)用最廣的隨機(jī)數(shù)生成算法是由Derrick Henry Lehmer1951年給出的線性同余法：
????????????? Xn+1 = ( aXn + c ) mod m,? n>=0.
在上一篇偽隨機(jī)數(shù)的論述中，并沒(méi)有給出X0, a, c, m的取值規(guī)則，只是給出了ANSI C和Microsoft Visual C++的實(shí)現(xiàn)。
在這兒我們可以自己先思考一下，我們期望從上式中得到的隨機(jī)數(shù)應(yīng)該滿足：
1) 上式的輸出足夠隨機(jī)，這是最基本的要求；
2) 上式給出盡量多的輸出，越接近m個(gè)越好（不可能超過(guò)m），即周期盡量長(zhǎng)，最好為m，這樣才能保證上式滿足均勻分布（m個(gè)數(shù)在周期m中各出現(xiàn)一次m個(gè)數(shù)出現(xiàn)的概率相等）；
3) 上式的生成速度足夠快。
最容易想到的，m的取值為計(jì)算機(jī)字大小（如2^32或2^64）。
但是這兒有個(gè)很嚴(yán)重的問(wè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甚至更短的同余序列。舉例說(shuō)明：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í)拋開(kāi)隨機(jī)性不管，先找到周期為m的隨機(jī)序列中的取值規(guī)則。
Donald Knuth在The Art of Computer Programming, Volume 2: Seminumerical Algorithms中的3.2.1.2節(jié)對(duì)m, a, c和X0取值規(guī)則的表述：
1) gcd(c, m) = 1. 即c, m互素，再白一點(diǎn)，c, m除1之外沒(méi)有其他公因子；
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è)證明過(guò)程對(duì)于我這樣的數(shù)論基礎(chǔ)不是很扎實(shí)的搞應(yīng)用技術(shù)的人來(lái)說(shuō)有點(diǎn)難以理解了。有興趣的話，還是去看3.2.1.2的證明吧:-)。
上面的規(guī)則告訴我們，滿足了上述規(guī)則后，可以保證序列周期為m。對(duì)于前面提到的關(guān)于隨機(jī)性的問(wèn)題，既然Xn低位的隨機(jī)性比較弱，可以只取Xn的高位作為輸出。高位的隨機(jī)性和統(tǒng)計(jì)意義由a, c確定，其取值涉及統(tǒng)計(jì)檢驗(yàn)，具體的也還是看3.3吧。
這篇文章解決了具有統(tǒng)計(jì)意義的隨機(jī)數(shù)的部分理論問(wèn)題。
PS: 之前曾經(jīng)BS過(guò)Windows Live Writer，當(dāng)時(shí)覺(jué)得Writer編輯功能太少，不能直接設(shè)定鏈接文字的字體顏色，知道CSS可以設(shè)定之后，又覺(jué)得Word 2007編輯的Blog轉(zhuǎn)成html之后太大，而且也知道Word 2007上面是可以設(shè)置鏈接的target為_(kāi)blank的。現(xiàn)在發(fā)現(xiàn)Writer還是很不錯(cuò)的了，原來(lái)是可以設(shè)定格式的，也可以直接編輯html，而且可以Web預(yù)覽，鏈接還可以加入到鏈接詞匯表，挺方便的。
越來(lái)越發(fā)現(xiàn)Wikipedia是個(gè)和Google一樣的好東西！