隨機(jī)數(shù)生成方法、隨機(jī)數(shù)生成法比較以及檢驗(yàn)生成的隨機(jī)序列的隨機(jī)性的方法

摘要本文著重討論了隨機(jī)數(shù)生成方法、隨機(jī)數(shù)生成法比較以及檢驗(yàn)生成的隨機(jī)序列的隨機(jī)性的方法。在隨機(jī)序列生成方面，本文討論了平方取中法、斐波那契法、滯后斐波那契法、移位法、線性同余法、非線性同余法、取小數(shù)法等，并比較了各方法的優(yōu)劣性。在統(tǒng)計(jì)檢驗(yàn)方面，介紹了統(tǒng)計(jì)檢驗(yàn)的方法，并用其檢驗(yàn)幾種隨機(jī)數(shù)生成器生成的隨機(jī)數(shù)的隨機(jī)性。最后介紹了兩種新的隨機(jī)數(shù)生成法，并統(tǒng)計(jì)檢驗(yàn)了生成隨機(jī)序列的隨機(jī)性。關(guān)鍵詞：隨機(jī)數(shù)，隨機(jī)數(shù)生成法，統(tǒng)計(jì)檢驗(yàn)ABSTRACTABSTRACTThisarticlefocusesonmethodsofrandomnumbergenerator,randomnumbergenerationmethodcomparisonandtesttherandomnessofthegeneratedrandomsequencemethod.Inrandomsequencegeneration,thearticlediscussesthesquaremethod,Fibonaccimethod,laggedFibonaccimethod,theshiftmethod,linearcongruentialmethod,linearcongruencemethod,takingminoritylaw,andComparisonofadvantagesanddisadvantagesofeachmethod.Instatisticaltest,theintroductionofthestatisticaltestmethod,andusedtotestsomerandomnumbergeneratorrandomrandomnumbersgenerated.Finally,twonewrandomnumbergenerationmethod,andstatisticaltestsofrandomnesstogeneratearandomsequence.KeyWords:randomnumber,randomnumbergenerator,statisticaltest目錄TOC\o"1-5"\h\z\o"CurrentDocument"第1章引言1\o"CurrentDocument"1.1課題背景1\o"CurrentDocument"1.2課題的價(jià)值及意義1\o"CurrentDocument"1.3課題的難點(diǎn)、重點(diǎn)、核心問(wèn)題及方向1\o"CurrentDocument"第2章隨機(jī)數(shù)3\o"CurrentDocument"2.1基本概念3\o"CurrentDocument"2.2產(chǎn)生隨機(jī)數(shù)的一般方法3\o"CurrentDocument"2.3隨機(jī)數(shù)生成的數(shù)學(xué)方法4\o"CurrentDocument"2.4產(chǎn)生隨機(jī)數(shù)的方法種類5\o"CurrentDocument"2.5隨機(jī)數(shù)的應(yīng)用6\o"CurrentDocument"第3章常見(jiàn)隨機(jī)數(shù)生成法與比較7\o"CurrentDocument"3.1平方取中法73.1.1迭代算法73.1.2平方取中法的優(yōu)缺點(diǎn)7\o"CurrentDocument"斐波那契(Fibonacci)法8\o"CurrentDocument"滯后斐波那契(Fibonacci)法9\o"CurrentDocument"3.4移位法9\o"CurrentDocument"3.5線性同余法10\o"CurrentDocument"3.5.1模數(shù)的選取103.5.2乘數(shù)的選取113.5.3線性同余法的缺陷123.5.4廣義線性同余法12\o"CurrentDocument"3.6非線性同余法133.6.1逆同余法133.6.2二次同余法143.6.3三次同余法143.6.4BBS法14\o"CurrentDocument"3.7取小數(shù)法14\o"CurrentDocument"3.8常見(jiàn)隨機(jī)數(shù)生成法的比較15\o"CurrentDocument"第4章隨機(jī)數(shù)生成法的統(tǒng)計(jì)和檢驗(yàn)16\o"CurrentDocument"4.1檢驗(yàn)類型16\o"CurrentDocument"4.2統(tǒng)計(jì)檢驗(yàn)的一般方法16\o"CurrentDocument"4.2.1參數(shù)檢驗(yàn)174.2.2均勻性檢驗(yàn)184.2.3重要分布18\o"CurrentDocument"4.2.4重要定理194.2.5卡方檢驗(yàn)204.2.6柯氏檢驗(yàn)204.2.7序列檢驗(yàn)21\o"CurrentDocument"4.3獨(dú)立性檢驗(yàn)22\o"CurrentDocument"4.4對(duì)線性同余法和取小數(shù)法進(jìn)行隨機(jī)性檢驗(yàn)22\o"CurrentDocument"第5章新的隨機(jī)數(shù)生成法24\o"CurrentDocument"5.1開方取小數(shù)法24\o"CurrentDocument"5.2一種混合型隨機(jī)數(shù)發(fā)生器285.2.1超素?cái)?shù)長(zhǎng)周期法285.2.2組合發(fā)生器的研究305.2.3隨機(jī)數(shù)算法統(tǒng)計(jì)檢驗(yàn)結(jié)果30\o"CurrentDocument"結(jié)束語(yǔ)32\o"CurrentDocument"參考文獻(xiàn)33\o"CurrentDocument"致謝34\o"CurrentDocument"外文資料原文35\o"CurrentDocument"翻譯文稿37第1章引言第1章引言1.1課題背景隨機(jī)數(shù)（隨機(jī)序列）在不同的領(lǐng)域有許多不同類型的應(yīng)用。如雷達(dá)中的測(cè)距信號(hào)，遙控遙測(cè)中的測(cè)控信號(hào)，數(shù)字通信中的群同步和加擾解擾信號(hào)，無(wú)線通信碼分多址系統(tǒng)中的擴(kuò)頻信號(hào)等都要用到隨機(jī)序列。在用計(jì)算機(jī)的教學(xué)與學(xué)習(xí)中，也經(jīng)常需要用到隨機(jī)數(shù)，比如，數(shù)據(jù)結(jié)構(gòu)中關(guān)于一個(gè)數(shù)據(jù)的存儲(chǔ)地址，在各種程序設(shè)計(jì)語(yǔ)言學(xué)習(xí)中遇到的隨機(jī)量的生成，圖像處理中遇到的隨機(jī)色彩的選擇等，枚不勝舉，隨機(jī)數(shù)在計(jì)算機(jī)的應(yīng)用中就顯得格外重要。尤其在仿真等領(lǐng)域，更對(duì)隨機(jī)數(shù)的產(chǎn)生提出了較高的要求，僅僅使用C語(yǔ)言類庫(kù)中的隨機(jī)函數(shù)已難以勝任相應(yīng)的工作?，F(xiàn)實(shí)中，用投色子計(jì)數(shù)的方法產(chǎn)生真正的隨機(jī)數(shù)，但電腦若也這樣做，將會(huì)占用大量?jī)?nèi)存；雖然用噪聲發(fā)生器或放射性物質(zhì)也可產(chǎn)生真正的隨機(jī)數(shù)，但操作不可重復(fù)。而用數(shù)學(xué)方法產(chǎn)生隨機(jī)數(shù)則最適合計(jì)算機(jī)，這就是“偽隨機(jī)數(shù)”。我們需要的隨機(jī)數(shù)序列應(yīng)具有非退化性，周期長(zhǎng)，相關(guān)系數(shù)小等優(yōu)點(diǎn)。迄今為止，研究人員提出了許多不同的隨機(jī)數(shù)生成方法，如平方取中法，同余法，斐波那契序列變形法，混沌序列法，利用系統(tǒng)時(shí)間和熱噪聲等等。隨著新的隨機(jī)數(shù)性能測(cè)試方法的提出，已經(jīng)證明其中的某些生成方法有其固有的缺陷。同時(shí)對(duì)測(cè)試方法的研究也是一個(gè)不斷發(fā)展的過(guò)程。1.2課題的價(jià)值及意義由于現(xiàn)在對(duì)隨機(jī)數(shù)的公認(rèn)定義中，只給出了隨機(jī)數(shù)的性質(zhì)描述，而沒(méi)有給出其生成方法，同時(shí)現(xiàn)有的所有檢測(cè)方法也只是給出了一些必要而非充分的條件。因此，隨機(jī)數(shù)的生成及其性能檢測(cè)方法，都有待于進(jìn)一步的研究。具體的應(yīng)用環(huán)境不同，對(duì)隨機(jī)數(shù)發(fā)生器的性能要求就不一樣，而不同的隨機(jī)數(shù)發(fā)生器產(chǎn)生的隨機(jī)數(shù)的性質(zhì)必然不一樣。為了能對(duì)一個(gè)隨機(jī)數(shù)發(fā)生器的性能做一個(gè)比較全面和客觀的評(píng)價(jià)，需要對(duì)不同的測(cè)試方法進(jìn)行研究，討論其測(cè)試目的和測(cè)試依據(jù)。本課題主要是討論隨機(jī)數(shù)生成法，隨機(jī)數(shù)生成法比較以及隨機(jī)數(shù)的檢測(cè)統(tǒng)計(jì)，從上面分析看出，本課題是很有意義和開拓性的工作。1.3課題的難點(diǎn)、重點(diǎn)、核心問(wèn)題及方向本課題的核心問(wèn)題是隨機(jī)數(shù)生成法、隨機(jī)數(shù)生成法比較以及隨機(jī)數(shù)的統(tǒng)計(jì)檢驗(yàn)。本課題的主要工作內(nèi)容如下：（1）介紹幾種常見(jiàn)的隨機(jī)數(shù)生成法，并比較了各種隨機(jī)數(shù)生成法的優(yōu)劣；（2）介紹統(tǒng)計(jì)檢驗(yàn)的理論，并對(duì)幾種隨機(jī)數(shù)生成法進(jìn)行了統(tǒng)計(jì)檢驗(yàn);(3)介紹新的隨機(jī)數(shù)生成法，并對(duì)隨機(jī)數(shù)進(jìn)行統(tǒng)計(jì)檢驗(yàn)。第2章隨機(jī)數(shù)在用計(jì)算機(jī)的教學(xué)與學(xué)習(xí)中，經(jīng)常需要用到隨機(jī)數(shù)，比如，數(shù)據(jù)結(jié)構(gòu)中關(guān)于一個(gè)數(shù)據(jù)的存儲(chǔ)地址，在各種程序設(shè)計(jì)語(yǔ)言學(xué)習(xí)中遇到的隨機(jī)量的生成，圖像處理中遇到的隨機(jī)色彩的選擇等，不勝枚舉，隨機(jī)數(shù)在計(jì)算機(jī)的應(yīng)用中就顯得格外重要。尤其在仿真等領(lǐng)域?qū)﹄S機(jī)數(shù)的產(chǎn)生提出了更較高的要求，僅僅使用C語(yǔ)言類庫(kù)中的隨機(jī)函數(shù)已難以勝任相應(yīng)的工作。現(xiàn)實(shí)中，用投色子計(jì)數(shù)的方法產(chǎn)生真正的隨機(jī)數(shù)，但電腦若也這樣做，將會(huì)占用大量?jī)?nèi)存；雖然用噪聲發(fā)生器或放射性物質(zhì)也可產(chǎn)生真正的隨機(jī)數(shù)，但操作不可重復(fù)。而用數(shù)學(xué)方法產(chǎn)生隨機(jī)數(shù)則最適合計(jì)算機(jī)，這就是“偽隨機(jī)數(shù)”。我們需要的隨機(jī)數(shù)序列應(yīng)具有非退化性，周期長(zhǎng)，相關(guān)系數(shù)小等優(yōu)點(diǎn)。2.1基本概念在密碼學(xué)中，對(duì)于一個(gè)隨機(jī)序列的定義如下：（1）看起來(lái)是隨機(jī)的。（2）這個(gè)序列是不可預(yù)測(cè)的。（3）這個(gè)序列是不能重復(fù)產(chǎn)生的。隨機(jī)變量門的抽樣序列叫,七,...七,...，稱為隨機(jī)數(shù)列。如果隨機(jī)變量門是均勻分布的，則門的抽樣序列氣，門2，'?氣，：，稱為均勻隨機(jī)數(shù)列；如果隨機(jī)變量門是正態(tài)分布的隨機(jī)變量則稱其抽樣序列為正態(tài)隨機(jī)數(shù)列。隨機(jī)序列具有以下性質(zhì)：（1）等分布性：隨機(jī)序列的分布特性是等概分布，或稱為一致分布。即是說(shuō)序列中每個(gè)元素出現(xiàn)的概率都是相等的。（2）獨(dú)立性：隨機(jī)序列的各個(gè)元素之間是相互獨(dú)立的。（3）不可預(yù)測(cè)性：該性質(zhì)可由等分布性和相互獨(dú)立性推出。（4）白噪聲譜特性：由獨(dú)立性可知，隨機(jī)序列的自相關(guān)函數(shù)為5函數(shù)。2.2產(chǎn)生隨機(jī)數(shù)的一般方法隨機(jī)數(shù)產(chǎn)生方法的研究己經(jīng)有很長(zhǎng)的歷史，至今仍有統(tǒng)計(jì)學(xué)者繼續(xù)研究隨機(jī)數(shù)產(chǎn)生的方法和理論。產(chǎn)生隨機(jī)數(shù)的一般方法：（1）手工方法:這是隨機(jī)數(shù)產(chǎn)生的最早方法，即采用抽簽、擲篩子、抽牌、搖號(hào)或從攪亂的罐子中取帶數(shù)字的球等方法。（2）隨機(jī)數(shù)表方法:Monte-Carlo方法的出現(xiàn)，需要大量的隨機(jī)數(shù)，顯然用手工的方法不能滿足模擬計(jì)算的需要d927年Tipett造出了具有4萬(wàn)個(gè)隨機(jī)數(shù)字的表;1939年Kendell和Babington-Smith用高速轉(zhuǎn)盤建立了有+萬(wàn)個(gè)數(shù)字的隨機(jī)數(shù)表;蘭德(Rand)公司利用電子裝置產(chǎn)生了含有一百萬(wàn)個(gè)數(shù)字的隨機(jī)數(shù)表。在電子計(jì)算機(jī)產(chǎn)生之前人們就是利用這些隨機(jī)數(shù)表進(jìn)行統(tǒng)計(jì)模擬計(jì)算。物理方法:隨著計(jì)算機(jī)和模擬方法的廣泛應(yīng)用，用計(jì)算機(jī)產(chǎn)生隨機(jī)數(shù)成為新的課題。在計(jì)算機(jī)上安裝一臺(tái)物理隨機(jī)數(shù)發(fā)生器，把具有隨機(jī)性質(zhì)的物理過(guò)程變換為隨機(jī)數(shù)，使用物理隨機(jī)數(shù)發(fā)生器在計(jì)算機(jī)上可以得到真正的隨機(jī)數(shù)，隨機(jī)性和均勻性都是很好的，而且是取之不盡用之不竭的。但是此方法也有一些缺點(diǎn)，其中最重要的是我們不能產(chǎn)生同原來(lái)完全相同的隨機(jī)數(shù)，對(duì)計(jì)算結(jié)果不能進(jìn)行復(fù)算檢查;加上物理隨機(jī)數(shù)發(fā)生器的穩(wěn)定性經(jīng)常需要進(jìn)行檢查和維修，因而大大降低了這種方法的使用價(jià)值。數(shù)學(xué)方法:它是利用數(shù)學(xué)遞推公式來(lái)產(chǎn)生隨機(jī)數(shù)的;它是目前使用最廣泛、發(fā)展很快的一類方法;它的特點(diǎn)是占用內(nèi)存少、速度快又便于計(jì)算。本文主要是介紹用數(shù)學(xué)方法來(lái)產(chǎn)生隨機(jī)數(shù)的算法，即各種各樣的隨機(jī)數(shù)發(fā)生器。2.3隨機(jī)數(shù)生成的數(shù)學(xué)方法用數(shù)學(xué)方法產(chǎn)生隨機(jī)數(shù)，就是利用計(jì)算機(jī)能直接進(jìn)行算術(shù)運(yùn)算或邏輯運(yùn)算的特點(diǎn)，選取一個(gè)適宜的數(shù)學(xué)遞推公式L+m=f(rnLm一1)，利用計(jì)算程序，按遞推公式對(duì)數(shù)字進(jìn)行加工處理，把0,1,…，七一1或其部分?jǐn)?shù)字的自然順序打亂，產(chǎn)生具有均勻總體、簡(jiǎn)單子樣統(tǒng)計(jì)性質(zhì)的隨機(jī)數(shù)，這里一般m取較小的正整數(shù)，力為機(jī)器的字長(zhǎng)。用數(shù)學(xué)方法產(chǎn)生的隨機(jī)數(shù)的速度快，占用內(nèi)存少，對(duì)模擬的問(wèn)題可以進(jìn)行復(fù)算檢查，一般還有較好的統(tǒng)計(jì)性質(zhì).但是，由于計(jì)算機(jī)只能表示有限位不同的數(shù)，嚴(yán)格說(shuō)，在計(jì)算機(jī)上不能產(chǎn)生真正連續(xù)分布的隨機(jī)數(shù)，只能產(chǎn)生離散分布的隨機(jī)數(shù)來(lái)代替連續(xù)分布的隨機(jī)數(shù).另外，計(jì)算機(jī)上用數(shù)學(xué)方法產(chǎn)生隨機(jī)數(shù)，是根據(jù)確定的算法推算出來(lái)的，因此嚴(yán)格說(shuō)來(lái)，用數(shù)學(xué)方法在計(jì)算機(jī)上產(chǎn)生的“隨機(jī)數(shù)”不能說(shuō)是真正的隨機(jī)數(shù)，故一般稱之為“偽隨機(jī)數(shù)”。隨機(jī)數(shù)生成方式有真隨機(jī)和偽隨機(jī)兩種。真隨機(jī)數(shù)生成法滿足以上關(guān)于隨機(jī)序列定義的所有三點(diǎn)要求，偽隨機(jī)數(shù)生成法只滿足前兩點(diǎn)要求。不過(guò)對(duì)這些偽隨機(jī)數(shù)，只要通過(guò)統(tǒng)計(jì)檢驗(yàn)符合一些統(tǒng)計(jì)要求，如均勻性、隨機(jī)性等，就可以作為真正的隨機(jī)數(shù)來(lái)使用。所以本文在后面章節(jié)將會(huì)介紹隨機(jī)數(shù)、隨機(jī)數(shù)生成法、隨機(jī)數(shù)生成法比較以及隨機(jī)數(shù)的統(tǒng)計(jì)檢驗(yàn)。在計(jì)算機(jī)上用數(shù)學(xué)方法產(chǎn)生隨機(jī)數(shù)的一般要求如下：產(chǎn)生的隨機(jī)數(shù)列要有均勻性、抽樣的隨機(jī)性、試驗(yàn)的獨(dú)立性和前后的一致性；產(chǎn)生的隨機(jī)數(shù)列要有足夠長(zhǎng)的周期，以滿足模擬實(shí)際問(wèn)題的要求；產(chǎn)生隨機(jī)數(shù)的速度要快，占用的內(nèi)存少。數(shù)學(xué)方法生成隨機(jī)數(shù)的過(guò)程如下：找到一個(gè)數(shù)學(xué)模型或算法。設(shè)置其中參數(shù)的值。通過(guò)某種運(yùn)算產(chǎn)生種子即第一個(gè)隨機(jī)數(shù)。然后在產(chǎn)生的種子的前提下，生成第二個(gè)隨機(jī)數(shù)。通過(guò)同樣的步驟，就產(chǎn)生了一個(gè)隨機(jī)數(shù)序列。從上可以看出，計(jì)算機(jī)中偽隨機(jī)數(shù)序列的產(chǎn)生有兩大要素，一是產(chǎn)生隨機(jī)數(shù)序列的初始值，稱之為隨機(jī)種子；二是產(chǎn)生隨機(jī)數(shù)的計(jì)算方法，即隨機(jī)函數(shù)。計(jì)算機(jī)的偽隨機(jī)數(shù)序列是由隨機(jī)種子根據(jù)一定的計(jì)算方法計(jì)算遞推出來(lái)的序列。偽隨機(jī)數(shù)生成器將作為“種子”的數(shù)當(dāng)作初始整數(shù)傳給函數(shù)。這粒種子會(huì)使這個(gè)球(生成偽隨機(jī)數(shù))一直滾下去。偽隨機(jī)數(shù)生成器的結(jié)果僅僅是不可預(yù)測(cè)。由偽隨機(jī)數(shù)生成器返回的每一個(gè)值完全由它返回的前一個(gè)值所決定，最終，該種子決定了一切。如果知道用于計(jì)算任何一個(gè)值的那個(gè)整數(shù)，那么就可以算出這個(gè)生成器返回的下一個(gè)值。結(jié)果，偽隨機(jī)數(shù)生成器是一個(gè)生成完全可預(yù)料序列的確定性程序。只要計(jì)算方法一定，隨機(jī)種子一定，那么程序每次產(chǎn)生的隨機(jī)數(shù)序列就是固定的。通常而言，計(jì)算方法是不容易改變的，而隨機(jī)種子是可以隨時(shí)改變的，程序每次運(yùn)行時(shí)可賦予不同的隨機(jī)種子從而得到不同的序列。2.4產(chǎn)生隨機(jī)數(shù)的方法種類由于產(chǎn)生隨機(jī)數(shù)的計(jì)算方法(隨機(jī)函數(shù))不同，現(xiàn)在大體有以下幾種常見(jiàn)方法：平方取中法、斐波那契法、滯后斐波那契法、移位法、線性同余法、非線性同余法、混沌序列法、取小數(shù)法等。一個(gè)好的隨機(jī)數(shù)發(fā)生器應(yīng)當(dāng)具備以下幾點(diǎn)條件：產(chǎn)生的隨機(jī)數(shù)序列要具有均勻總體隨機(jī)樣本的統(tǒng)計(jì)性質(zhì)，如分布的均勻性，抽樣的隨機(jī)性，數(shù)列間的獨(dú)立性等等。(經(jīng)驗(yàn)檢驗(yàn))產(chǎn)生的隨機(jī)數(shù)序列要具有較好的理論支持(或具有好的格結(jié)構(gòu))，如分布的譜檢驗(yàn)(Spectraltest)和高維分布檢驗(yàn)(k-distributiontest)。(理論檢驗(yàn))產(chǎn)生的隨機(jī)數(shù)序列要有足夠長(zhǎng)的周期，以滿足模擬計(jì)算的需要。產(chǎn)生的隨機(jī)數(shù)序列的速度快，占用計(jì)算機(jī)的內(nèi)存少，具有完全可重復(fù)性。隨著計(jì)算機(jī)運(yùn)算速度的不斷提高，存儲(chǔ)容量和字長(zhǎng)的不斷擴(kuò)大，(3)和((4)兩點(diǎn)一般都能滿足;至于條件(2)屬于理論方面的問(wèn)題，由于涉及到很多數(shù)論等基礎(chǔ)數(shù)學(xué)方面的內(nèi)容，本文不做過(guò)多的研究。因此，關(guān)鍵是如何構(gòu)造滿足(1)的隨機(jī)數(shù)發(fā)生器，即做大量的統(tǒng)計(jì)檢驗(yàn)工作。下面章節(jié)將詳細(xì)介紹各方法，并分析比較各方法的優(yōu)缺點(diǎn)，最后對(duì)各方法做統(tǒng)計(jì)檢驗(yàn)工作。2.5隨機(jī)數(shù)的應(yīng)用隨機(jī)序列有許多不同類型的應(yīng)用。諸如用于仿真各種自然現(xiàn)象，用于檢驗(yàn)計(jì)算機(jī)程序設(shè)計(jì)中的隨機(jī)化算法，甚至有時(shí)候被人們用來(lái)做決策。同時(shí)隨著計(jì)算機(jī)技術(shù)、通信技術(shù)的充分發(fā)展，信息在傳遞、處理、存儲(chǔ)過(guò)程中的安全問(wèn)題已引起了人們的廣泛關(guān)注.信息安全領(lǐng)域內(nèi)的核心問(wèn)題之一就是如何制作高質(zhì)量的隨機(jī)數(shù)發(fā)生器和產(chǎn)生隨機(jī)數(shù)的方法。現(xiàn)在，隨機(jī)數(shù)已廣泛應(yīng)用于在密碼算法方面、安全協(xié)議方面、數(shù)字水印方面等信息安全領(lǐng)域在很多情況下，系統(tǒng)決策需要進(jìn)行多次仿真比較才能確定，重現(xiàn)性非常必要。因此，在計(jì)算機(jī)上生成偽隨機(jī)數(shù)及對(duì)偽隨機(jī)數(shù)進(jìn)行檢驗(yàn)的問(wèn)題就受到人們的重視。模擬計(jì)算表明，通過(guò)改進(jìn)偽隨機(jī)數(shù)的品質(zhì)，可使計(jì)算機(jī)仿真結(jié)果的有效性得到明顯提高，在有些情況下甚至可使仿真結(jié)果的數(shù)值相對(duì)誤差縮小為原來(lái)的1/10或更小。因此，進(jìn)行偽隨機(jī)數(shù)發(fā)生器的研究，具有重要的理論意義和應(yīng)用價(jià)值。第3章常見(jiàn)隨機(jī)數(shù)生成法與比較由于產(chǎn)生隨機(jī)數(shù)的計(jì)算方法（隨機(jī)函數(shù)）不同，現(xiàn)在大體有以下幾種常見(jiàn)方法：平方取中法、斐波那契法、滯后斐波那契法、移位法、線性同余法、非線性同余法、混沌序列法、取小數(shù)法等。3.1平方取中法產(chǎn)生偽隨機(jī)數(shù)列最早的方法是平方取中法，它是由馮?諾依曼提出的。3.1.1迭代算法此法開始取一個(gè)2s位的整數(shù)，稱為種子，將其平方，得4s位整數(shù)（不足4s位的高位補(bǔ)0），然后取此4s位的中間2s位作為下一個(gè)種子數(shù)，重復(fù)上述過(guò)程，即可得到一系列隨機(jī)數(shù)。平方取中法的遞推公式為：TOC\o"1-5"\h\zX=[X2/10s]（mod102s）（3-1）n+1n產(chǎn)生偽隨機(jī)數(shù)列：r=x/102s（3-2）3.1.2平方取中法的優(yōu)缺點(diǎn)平方取中法的優(yōu)點(diǎn)為在計(jì)算機(jī)上易于實(shí)現(xiàn)，內(nèi)存占用少，但仍存在對(duì)小數(shù)目偏倚的現(xiàn)象，均勻性不好，對(duì)初始數(shù)據(jù)的依賴很大，數(shù)列的長(zhǎng)度和周期難以確定，很容易出現(xiàn)重復(fù)元素的短循環(huán)，而且，一旦某個(gè)元素是0，則后面所有的元素都將是0。如果生成的序列中，有從最高位開始連續(xù)s個(gè)0的數(shù)，則產(chǎn)生的序列會(huì)逐漸退化為0。這是因?yàn)樵谑M(jìn)制表示的情況下：r<10s,r2vrx10s,則由（3-1）可得r1<ro或者生成的序列中，有從最低位起至少連續(xù)的甬+1個(gè)0的數(shù)，則產(chǎn)生的序列也會(huì)逐漸退化到0。這是因?yàn)椋喝绻尚蛄兄衦滿足上述條件，則了從末位起至少有2s+2個(gè)0，即是說(shuō)二末位的0比r+i1末位的0多，從而逐漸退化為全0。

當(dāng)生成的序列中，有從最低位起有連續(xù)的S個(gè)0的數(shù)，則生成的序列元素，從最低位起，有一半的位為0。它的最長(zhǎng)周期已由2S退化為S，這樣的數(shù)，已不適合再稱為偽隨機(jī)數(shù)。平方取中法有一些變形和推廣。其中之一就是：后一個(gè)序列元素不再只依賴于前一個(gè)元素，而是依賴于前幾個(gè)，甚至是不相鄰的幾個(gè)序列元素。這種變形和推廣使得序列的周期長(zhǎng)度通常大于2S，但產(chǎn)生的序列的隨機(jī)性需要經(jīng)過(guò)檢驗(yàn)。另一種就是對(duì)平方取中法進(jìn)行改進(jìn)的方法是，乘積取中法，如果要產(chǎn)生具有1O進(jìn)制2位的偽隨機(jī)數(shù)列，任取兩個(gè)初始隨機(jī)數(shù)％氣，用遞推公式：x2=[x1x/10s]（mod102s）（3-3）產(chǎn)生偽隨機(jī)數(shù)列：r=x/102s（3-4）乘積取中法與平方取中法比較，從產(chǎn)生的偽隨機(jī)數(shù)列長(zhǎng)度及均勻性方面都有改善，但是數(shù)列長(zhǎng)度還是不夠，而且對(duì)初始值的依賴性很大。3.2斐波那契（Fibonacci）法斐波那契法是基于Fibonacci序列，其遞推公式為：(n=1,2,…)（3-5）=(x+x)modmxr=f(n=1,2,…)（3-5）顯然，斐波那契法有兩個(gè)初始種子x0和x1。方法的最大特點(diǎn)就是計(jì)算速度很快，且達(dá)到滿周期。但是序列中數(shù)重復(fù)出?，F(xiàn)，'獨(dú)立性較差。此發(fā)生器沒(méi)有乘法運(yùn)算，產(chǎn)生速度快.但是它存在著令人不能容忍的不居中現(xiàn)象，即由前兩個(gè)數(shù)得到的第三個(gè)數(shù)要不是同時(shí)大于就是同時(shí)小于前二者而永不居中。此序列的另一個(gè)缺點(diǎn)是顯著的序列相關(guān)，即取小值的數(shù)后面出現(xiàn)也取小值的趨勢(shì)。所有這些都說(shuō)明它不是一個(gè)好的隨機(jī)數(shù)序列。

3.3滯后斐波那契（Fibonacci）法滯后的斐波那契法是斐波那契法的推廣，目前存在很多種形式。下面僅僅給出一種比較有名的方法，其遞推公式為：(n=0,1,…)（3-6）x=(x(n=0,1,…)（3-6）xr=f〔nm其中p>q>0，初始種子為（x「x2，…,x）。3.4移位法計(jì)算機(jī)善于進(jìn)行移位等邏輯運(yùn)算，應(yīng)用計(jì)算機(jī)的這個(gè)特點(diǎn)有一類產(chǎn)生偽隨機(jī)數(shù)列的方法，該方法稱為移位法。本方法是關(guān)于平方取中法的一種改進(jìn)形式，它是移位運(yùn)算與指令相加運(yùn)算相結(jié)合的迭代過(guò)程。TOC\o"1-5"\h\z它的思想是：首先選取一個(gè)初始值x，使之左右移位，分別為x和x，然后00102指令相加得氣，再對(duì)氣進(jìn)行上述過(guò)程，如此重復(fù)下去，便可得隨機(jī)數(shù)序列。對(duì)于字長(zhǎng)為32位的計(jì)算機(jī)，，這一算法的遞推公式為：x=27x+2-7x（mod232）（3-7）產(chǎn)生偽隨機(jī)數(shù)列：r=x/232（3-8）移位法運(yùn)算速度快，但是對(duì)初始值的依賴性也很大，一般地初始值不能取得太小，選得不好會(huì)使偽隨機(jī)數(shù)列長(zhǎng)度較短。同時(shí)m（m>1）維均勻隨機(jī)向量相關(guān)性大，即獨(dú)立性較差。最后隨機(jī)數(shù)序列周期廣與計(jì)算機(jī)的字長(zhǎng)有關(guān)。3.5線性同余法同余法(LinearCongruentialGenerator,LCGforshort)是Lehmer于1951年提出來(lái)的，此方法是利用數(shù)論中的同余運(yùn)算原理來(lái)產(chǎn)生隨機(jī)數(shù)，有線性同余法、非線性同余法等，其中線性同余法法又分為加同余法、乘同余法以及混合同余法。同余法是現(xiàn)在發(fā)展迅速且使用普遍的方法之一。首先介紹下線同余法。線性同余法的遞推式為：工=ax+c(modm)(n=0,1,2,?.?)(3-9)式中參數(shù)a,c和m分別稱為乘、增量和模，X0為種子。如果這些參數(shù)和種子(初值)都指定序列也就確定下來(lái)了。通常取r=%(n=0,1,2,..?)作為區(qū)間(O，1)上均勻nm分布U(0,1)的隨機(jī)數(shù)。從上可以看出當(dāng)c=0，為乘同余法；當(dāng)a=1,c豐0時(shí)，為加同余法，否則稱為混合同余法。按慣例，當(dāng)強(qiáng)調(diào)使用某方法產(chǎn)生隨機(jī)數(shù)時(shí)，常使用某方法(隨機(jī)數(shù))發(fā)生器的稱呼。線性同余法有如下特點(diǎn)：0<x<m+1。適當(dāng)選取m,a,c可使Xj循環(huán)，無(wú)論x0取何值，其循環(huán)順序相同，其循環(huán)周期稱為發(fā)生器周期，記為T'。若T=m，則稱之為滿周期。適當(dāng)選取m,a,c，可保證xj在[[0,1)區(qū)間上一個(gè)周期內(nèi)每個(gè)整數(shù)正好出現(xiàn)一次，從而保證了均勻性?！癁樘岣遰的均勻性，要求加大m。j下面討論下線性同余中參數(shù)的選取。3.5.1模數(shù)的選取從線性同余的生成公式中可以看到，生成序列X的最長(zhǎng)周期不可能超過(guò)m。為得到較長(zhǎng)的周期，需要選擇較大m值。考慮m的另一個(gè)方面是實(shí)現(xiàn)時(shí)的生成速度。在二進(jìn)制計(jì)算機(jī)上，進(jìn)行模運(yùn)算，最好選擇模數(shù)m=2e的形式。這樣模運(yùn)算，只需要進(jìn)行位與操作就可以實(shí)現(xiàn)了。但是這種簡(jiǎn)單的選擇，在某些應(yīng)用中，卻不是令人滿意的。這里，假設(shè)選取m=2e，則d=24是m的一個(gè)因子。這里d的指數(shù)選取為4是因?yàn)槲覀兗僭O(shè)只考察生成序列元素x的最低四個(gè)比特位的規(guī)律。y=x(modd)(3-10)y=x(modd)-(ax+c)(modd)=(ay+c)(modd)(3-11)n+1n+1nn可以看到，由序列氣的各元素低三比特位組成的序列是一個(gè)周期更短的同余序列。它的最長(zhǎng)周期為16。類似的，氣低三位的最長(zhǎng)周期為8，氣低五位的最長(zhǎng)周期為32，等等。氣的最低位不是常數(shù)，，就是O,1交替。這在強(qiáng)調(diào)低位隨機(jī)性的應(yīng)用中，是不令人福意的。為避免這種缺陷，可以選擇模數(shù)m=2e±1，或者是選取m為小于2e的最大素?cái)?shù)。對(duì)于模數(shù)m=2e+1的情況，(xmodm)有快速實(shí)現(xiàn)方法(見(jiàn)附錄)：注意上述算法中，第7步其實(shí)是一個(gè)遞歸調(diào)用。整個(gè)算法中只有加減，位與，移位，比較和跳轉(zhuǎn)操作。對(duì)于m=2e-1的情況也是類似的。3.5.2乘數(shù)的選取模數(shù)m取得較大，序列的周期才可能較大。下面的定理1指出了得到極大周期所應(yīng)滿足的條件：由m,a,c和xo所定義的線性同余序列有周期長(zhǎng)度m，當(dāng)且僅當(dāng)：c與m互素；對(duì)于整除m的每個(gè)素?cái)?shù)p，b=a-1是p的倍數(shù)；如果m三0(mod4)，則b三0(mod4)。該定理的證明過(guò)程見(jiàn)附錄。在有些情況下，可能會(huì)利用c=0(此時(shí)為乘同余法)來(lái)獲得較快的生成速度。根據(jù)定理1,這時(shí)生成序列不可能達(dá)到極大周期聊。但仍然可以通過(guò)選擇乘數(shù)a來(lái)使得序列周期盡可能地長(zhǎng)。在生成公式(3-9)中，取c=0，m=pe，則x三anx(modpe)(3-12)顯然，周期是使得x0=arx0(modpe)的最小正整數(shù)T。如果x°與pe的最大公因子是pf，則由數(shù)論定理，得到：°aT=1(modpe-f)(3-13)由數(shù)論歐拉定理可知：gpe-f)三1(modpe-f)(3-14)所以，T必是甲(pe-f)的一個(gè)因子。欲使得T為最大，應(yīng)當(dāng)取T等于甲(pe-f).且若x0與pe互素，則此時(shí)T等于甲(pe-f)=pe-1(p-1)。并且當(dāng)a是模m的一個(gè)本原元時(shí)，aT=1(modm)中T取得極大值甲(m)。綜上所述，得出下面的結(jié)論：當(dāng)c=0時(shí)，生成序列可能達(dá)到的極大周期等于模數(shù)們的歐拉函數(shù)甲(m)，若滿足：初始值X0與m互素；乘數(shù)a是模m的一個(gè)本原元，則可以實(shí)現(xiàn)這一周期。3.5.3線性同余法的缺陷線性同余序列眾所周知的缺陷是其高維稀疏網(wǎng)格結(jié)構(gòu)：當(dāng)把相繼的t個(gè)隨機(jī)數(shù)(r,r，…,r)，看作是m維空中上的一個(gè)點(diǎn)時(shí)，這些點(diǎn)只散布在m維空間的的nn+1n+m少數(shù)幾個(gè)超平面上，并形成稀疏的網(wǎng)格結(jié)構(gòu)。為說(shuō)明線性同余法的問(wèn)題，首先給出一個(gè)極簡(jiǎn)單的線性同余發(fā)生器：x=14x(mod17)(n=0,1,2,..?)，其中r=x/m(n=0,1,2,?.?)被看作是(0,1)上的隨機(jī)數(shù)。當(dāng)％=1時(shí)，它產(chǎn)生周期為16的如下序列1，14,9,7,13,l2，15，6，l6，3，8，l0，4，5，2，ll，1.容易看出，x=17-x，即其前半段與后半段的相關(guān)系數(shù)為一1，這便是同余發(fā)生器的長(zhǎng)周期相關(guān)現(xiàn)?：MatteisPagnuttir已從理論上證明了所有線性和非線性同余序列都存在長(zhǎng)周期相關(guān)現(xiàn)象。在應(yīng)用中，我們應(yīng)特別警惕和回避這種現(xiàn)象。如果幾個(gè)并行處理器分別使用同一個(gè)同余序列的不同段落，分割時(shí)就應(yīng)避開具有強(qiáng)相關(guān)的分點(diǎn)。3.5.4廣義線性同余法廣義線性同余發(fā)生器(Generalizedlinearcongruentialgenerator,GLCGforshort)是線性同余發(fā)生器的推廣，其遞推公式為：x=f(x?,x，…，x)(modm)(n=0,1,…)(3-15)n+knn+1n+k-1

其中f是氣?,氣,「???,氣,^1的確定性函數(shù)。3.6非線性同余法80年代末開始，許多學(xué)者已經(jīng)開始討論非線性同余發(fā)生器(Nonlinearcongruentialgenerator,NLCGforshort)，其遞推公式的一般形式為：x=f(x)(modm)<n+1L(n=0,1，…)(3-16)r=f〔nm公式(3-17)中的xeZ={0,1...,m-1}，而f是Z上的一個(gè)整數(shù)函數(shù)。若f(氣)=%+C，則公式(3-17)就是線性同余發(fā)生器。在非線性同余中f是Zm上的一個(gè)排列多項(xiàng)式，這時(shí)有{f(0),f(1),…,f(m-1)}=Zm。W下面介紹幾種比較典型的非線性同余發(fā)生器:逆同余法、二次同余法、三次同余法和BBS法。3.6.1逆同余法逆同余發(fā)生器(Inversivecongruentialgenerator,ICGforshort)，是非線性同余類中的最有前途的一種隨機(jī)數(shù)發(fā)生器。其遞推公式為：Xn=(aX+b)mod(n=0,1,2...)(3-17)xnm其中對(duì)于ceZ(m為素?cái)?shù))，定義cC=1modm且ceZ(若c=0，定義c=0)Xn=(aX+b)mod(n=0,1,2...)(3-17)x逆同余法的主要優(yōu)點(diǎn)在于能克服高維網(wǎng)格結(jié)構(gòu).例如模為M=231-1的逆同余發(fā)生器可以通過(guò)直至230維的網(wǎng)格檢驗(yàn).而線性同余發(fā)生器要保證10維以內(nèi)近似最優(yōu)的網(wǎng)格結(jié)構(gòu)都有困難(請(qǐng)參考Fishman—Moore，1986).然而逆同余法的周期不比線性同余法的長(zhǎng)，Matteis-Pagnutti(1990)也從理論上證明了所有逆同余序列也都象線性同余序列那樣存在長(zhǎng)周期相關(guān)現(xiàn)象。另外，從應(yīng)用上看，逆同余法的速度明顯慢于線性同余。3.6.2二次同余法二次同余的生成表達(dá)式：x=(dx2+ax+c)(modm)(3-18)上式產(chǎn)生的序列有周期長(zhǎng)度m，當(dāng)目?jī)H當(dāng)：c與m互素，對(duì)所有整除m的奇素?cái)?shù)p，d和a-1都是p的倍數(shù)；如果m是4的倍數(shù)，則d是偶數(shù)，而且d三a-1(mod4):如果m是2的倍數(shù)，則d三a-1(mod2)；如果m是9的倍數(shù)，則dMc(mod9).二次同余是一般線性同余的推廣，由以上的結(jié)論可以看出，要獲得極大周期m所需的條件限制并不比線性同余法更嚴(yán)格。3.6.3三次同余法三次同余的生成表達(dá)式：x=(ax3+bx2+cx+d)(modm)(3-19)其中a,b,c,d均為正整數(shù)，且a公0，m為正整數(shù)模，x0為初始種子。數(shù)a、c、m的取值滿足一定條件時(shí),才可得到較好結(jié)果。3.6.4BBS法BBS發(fā)生器是由Blum和Shub共同提出的一種隨機(jī)數(shù)發(fā)生器。其遞推公式x.=x2modm(i=0,1,2...)(3-20)3.7取小數(shù)法這種方法不能直接用公式表達(dá)，其原理是將前一次隨機(jī)數(shù)平方后的數(shù)，取其小數(shù)點(diǎn)后第一個(gè)非零數(shù)字后面的尾數(shù)作為下一個(gè)所求的隨機(jī)數(shù)。3.8常見(jiàn)隨機(jī)數(shù)生成法的比較前面介紹各種隨機(jī)數(shù)生成法時(shí)，已經(jīng)大概介紹了下各種方法的優(yōu)缺點(diǎn)?，F(xiàn)在再簡(jiǎn)要比較下各種隨機(jī)數(shù)生成法的優(yōu)缺點(diǎn)。平方取中法的優(yōu)點(diǎn)是計(jì)算簡(jiǎn)單，計(jì)算機(jī)上易于實(shí)現(xiàn)，內(nèi)存占用少，缺點(diǎn)是種子的選擇很重要，對(duì)初始數(shù)據(jù)的依賴很大，否則很難保證有足夠長(zhǎng)的周期，而且容易出現(xiàn)退化現(xiàn)象(以后的隨機(jī)數(shù)為同一常數(shù)或?yàn)?)。斐波那契法的優(yōu)點(diǎn)是計(jì)算簡(jiǎn)單,計(jì)算速度很快，周期較長(zhǎng)且達(dá)到滿周期，可證明為1.5m。缺點(diǎn)序列中數(shù)重復(fù)出現(xiàn)，獨(dú)立性較差。此發(fā)生器沒(méi)有乘法運(yùn)算，產(chǎn)生速度快.但是它存在著令人不能容忍的不居中現(xiàn)象，即由前兩個(gè)數(shù)得到的第三個(gè)數(shù)要不是同時(shí)大于就是同時(shí)小于前二者而永不居中。此序列的另一個(gè)缺點(diǎn)是顯著的序列相關(guān)，即取小值的數(shù)后面出現(xiàn)也取小值的趨勢(shì)。所有這些都說(shuō)明它不是一個(gè)好的隨機(jī)數(shù)序列。移位法運(yùn)算速度快，但是對(duì)初始值的依賴性也很大，一般地初始值不能取得太小，選得不好會(huì)使偽隨機(jī)數(shù)列長(zhǎng)度較短。同時(shí)m(m1)維均勻隨機(jī)向量相關(guān)性大，即獨(dú)立性較差，存在稀疏網(wǎng)格，最后隨機(jī)數(shù)序列周期T與計(jì)算機(jī)的字長(zhǎng)有關(guān)。線性同余法是一種較好的方法，目前很多仿真語(yǔ)言中使用的就是這種方法。其缺點(diǎn)是高維稀疏網(wǎng)格結(jié)構(gòu)，有長(zhǎng)周期相關(guān)現(xiàn)象，相對(duì)而言其計(jì)算要復(fù)雜些，而且只有公式中的常數(shù)m,a,c的取值滿足一定條件時(shí)，才可得到較好結(jié)果。非線性及逆同余的缺陷是長(zhǎng)周期相關(guān)，周期依賴機(jī)器字長(zhǎng)，產(chǎn)生效率低。取小數(shù)法的優(yōu)缺點(diǎn)類似于平方取中法，而且要求種子一般應(yīng)取純小數(shù)，并且數(shù)字位要盡量多。第4章隨機(jī)數(shù)生成法的統(tǒng)計(jì)和檢驗(yàn)隨機(jī)數(shù)的好壞如何，即它們的性質(zhì)究竟與真正的［0,1］區(qū)間上的均勻分布的隨機(jī)變量的簡(jiǎn)單隨機(jī)樣本的性質(zhì)有無(wú)顯著差異，是一個(gè)很重要的問(wèn)題。如果有顯著差異，則以這種隨機(jī)數(shù)發(fā)生器產(chǎn)生的隨機(jī)數(shù)為基礎(chǔ)的隨機(jī)變量所抽得的樣本，實(shí)際上將不能反映該隨機(jī)變量的性質(zhì)，從而所得隨機(jī)模擬的最后的結(jié)果將是不可靠的。因此對(duì)隨機(jī)數(shù)進(jìn)行檢驗(yàn)，將是很重要的工作。在進(jìn)行統(tǒng)計(jì)檢驗(yàn)之前，下面首先簡(jiǎn)單介紹一些統(tǒng)計(jì)檢驗(yàn)的基礎(chǔ)知識(shí)。4.1檢驗(yàn)類型一般情況下有兩種不同的檢驗(yàn)方法：經(jīng)驗(yàn)檢驗(yàn):經(jīng)驗(yàn)檢驗(yàn)是一種統(tǒng)計(jì)檢驗(yàn)，它是以發(fā)生器產(chǎn)生的均勻隨機(jī)數(shù)序列｛土｝為基礎(chǔ)的，根據(jù)［0，1］區(qū)間上均勻總體簡(jiǎn)單隨機(jī)樣本｛七｝的性質(zhì)，如特征向量、均勻性、隨機(jī)性等，研究我們產(chǎn)生的隨機(jī)數(shù)序列｛勺的相應(yīng)性質(zhì)，進(jìn)行比較、鑒別、視其差異是否顯著，決定取舍。理論檢驗(yàn):理論檢驗(yàn)從統(tǒng)計(jì)意義上講并不是一種檢驗(yàn)。它是一種綜合的方法來(lái)評(píng)估發(fā)生器的數(shù)值參數(shù)，而根本不必產(chǎn)生任何隨機(jī)數(shù)序列｛土｝，即它是一種理論上的研究。本章主要介紹一些經(jīng)驗(yàn)檢驗(yàn)，對(duì)于理論檢驗(yàn)由于涉及過(guò)多的專門學(xué)科的知識(shí)，數(shù)學(xué)上相當(dāng)困難的，本章不再給予討論。4.2統(tǒng)計(jì)檢驗(yàn)的一般方法統(tǒng)計(jì)檢驗(yàn)的一般方法有以下幾種：參數(shù)檢驗(yàn):均勻隨機(jī)數(shù)的參數(shù)檢驗(yàn)是檢驗(yàn)由某個(gè)發(fā)生器產(chǎn)生的隨機(jī)數(shù)序列｛土｝的均值、方差和各階矩等與均勻分布的理論值是否有顯著的差異。均勻性檢驗(yàn):隨機(jī)數(shù)的均勻性檢驗(yàn)又稱頻率檢驗(yàn)，它是來(lái)檢驗(yàn)由某個(gè)發(fā)生器產(chǎn)隨機(jī)數(shù)序列｛土｝時(shí)，是否均勻地分布在區(qū)間［0，1］上。也就是檢驗(yàn)經(jīng)驗(yàn)頻率與理論頻率的差異是否顯著。獨(dú)立性檢驗(yàn):獨(dú)立性檢驗(yàn)主要是檢驗(yàn)隨機(jī)數(shù)序列％七…七之間的統(tǒng)計(jì)相關(guān)性是否顯著。即判別每個(gè)數(shù)的出現(xiàn)是否與其前后各數(shù)獨(dú)立無(wú)關(guān)。

（4）無(wú)連貫性檢驗(yàn)：將依次出現(xiàn)的"偽隨機(jī)數(shù)，按其大小分為兩類或者*類，則各類數(shù)的出現(xiàn)是否有連貫現(xiàn)象。對(duì)于參數(shù)檢驗(yàn)，由于隨機(jī)數(shù)服從標(biāo)準(zhǔn)均勻分布U（°，1）,則其均值和方差的理論值分別為：口=°.5,b2=1/12（4-1）當(dāng)樣本容量充分大時(shí)，可用正態(tài)分布進(jìn)行檢驗(yàn)。利用％2擬合優(yōu)度檢驗(yàn)（取1°個(gè)區(qū)間）可以檢驗(yàn)所產(chǎn)生的隨機(jī)樣本的總體分布是否為均勻分布。利用游程檢驗(yàn)法檢驗(yàn)隨機(jī)樣本的獨(dú)立性，其中游程是由連續(xù)°或者1組成的序列，并且其前后元素與游程的元素不同.游程數(shù)日為序列長(zhǎng)度的一半產(chǎn)生的隨機(jī)序列較好。4.2.1參數(shù)檢驗(yàn)若隨機(jī)變量R?U（0,1），則E（R）=上,Var（R）=—,E（R2）=1,若R,R,...,R是212312〃均勻總體的簡(jiǎn)單隨機(jī)樣本，即R1,R2,...,Rn相互獨(dú)立同U（0,1）分布。記R=：&,

i=1R2=1&2，S2=1芝[R-1]2ni=1"i2JE（RR=：&,

i=1E（R）1=—，2Var（R^=—；12nE（R2）=1，3Var（R2）=土；

45nVar（s2）=」-18°n設(shè)r,r，…,r是某個(gè)發(fā)生器產(chǎn)生的隨機(jī)數(shù)。首先對(duì)特征量作統(tǒng)計(jì)檢驗(yàn)。在｛r｝是均勻E（R2）=1，3Var（R2）=土；

45n12ni總體的簡(jiǎn)單隨機(jī)樣本的假設(shè)下，統(tǒng)計(jì)量：u=r=4^=可fr-g^var^DI2）_1r2-3h頑—方2Var1s2——/i、一A-畋s2—-V127u3.^Var\s2)漸進(jìn)服從N（0,1）。給定顯著水平a后，查標(biāo)準(zhǔn)正態(tài)數(shù)值表得：人:P,u|a人｝=a,（u?N（0,1）），否定域W—,u|q｝（i=1,2,3）。由隨機(jī)數(shù)列｛r｝計(jì)算u,u：u的值，若iu|〈人，則認(rèn)為產(chǎn)生的隨機(jī)數(shù)序列的特征量與均勻總體的特征1231i-1量沒(méi)有顯著差異；否則由于n｝得特征量與均勻總體特征量有顯著差異，故不能認(rèn)為｛r｝是均勻總體的簡(jiǎn)單樣本。i4.2.2均勻性檢驗(yàn)均勻性檢驗(yàn)中常用的方法有:卡方檢驗(yàn)、柯氏檢驗(yàn)和序列檢驗(yàn)。4.2.3重要分布（1）二項(xiàng)分布：如果隨機(jī)變量x的所有可能取值為k=0,1,2,,n，且x取值k的概率為p=Ckpk(1—p)n—k，k=0,1,2,???，n(4-2)則稱x服從參數(shù)為n,p的二項(xiàng)分布，記為x?B（n,p）。當(dāng)k取值僅為0,1時(shí)，又稱x服從0-1分布或兩點(diǎn)分布。（2）正態(tài)分布：如果隨機(jī)變量X的概率密度函數(shù)為：2b2（4-3）則稱隨機(jī)變量X服從參數(shù)為(四q2)的正態(tài)分布，記為X?N(四,c2)。如果口=0,。=1，則稱X服從正態(tài)分布，記為X?N偵c2)。其分布函數(shù)記為：(4-4)①(z)=人fe-u22du、；2兀-8(4-4)%2分布設(shè)氣,％,...,x.是來(lái)自于標(biāo)準(zhǔn)正態(tài)總體N(0,1)的獨(dú)立樣本，則由它們構(gòu)造的統(tǒng)計(jì)量X=云X2服從自由度為n的％2分布。自由度為n的%2分布的概率密度函數(shù)為:i=1Xn/2-1e-x/2/、1A(4-5)f(x,n)=\2n/2r(n/2)0其中伽瑪函數(shù)r(z)=8xz-le-xdx，而Y(a)=「(a,0)。Xn/2-1e-x/2(4-5)對(duì)一般的伽瑪函數(shù)，有「(a,x)=8ta-ie-tdt。特別地，對(duì)于a為整數(shù)n的情況，有:(4-6)r(n,x)=(n-1)!e-xZ1—k!(4-6)k=04.2.4重要定理(1)Pearson定理利用總體的樣本值x1%,...,x來(lái)檢驗(yàn)總體的分布函數(shù)是否為F(x)。先設(shè)定原假設(shè)H0:X的分布函數(shù)為F(x)，F(xiàn)(x)為某已知分布函數(shù)。取k-1個(gè)點(diǎn)，滿足：tYtY...Yt將實(shí)數(shù)軸分為k個(gè)區(qū)間：(-8,t],(t,t],...,(t,+8)。設(shè)TOC\o"1-5"\h\z12k-1/112k-1樣本值x,x,...x中落入第i個(gè)區(qū)間(t,t]內(nèi)的個(gè)數(shù)為V，其相對(duì)頻數(shù)為12ni-1itv/n,(1<i<k)。'如果原假設(shè)H0成立，則X落入第1個(gè)區(qū)間內(nèi)的概率為：\o"CurrentDocument"p=F(t)-F(t.「,1<i<k(4-7)

貝努利定理指出：當(dāng)n-8,重復(fù)獨(dú)立實(shí)驗(yàn)中事件發(fā)生的頻數(shù)收斂于該事件在每次試驗(yàn)中發(fā)生的概率。所以當(dāng)n充分大時(shí)候，n-pt應(yīng)該比較小。從而得出習(xí)匕-p?_!=￡"2也應(yīng)該較小。,=15')P,=1nPPearson指出：假設(shè)H°成立，則當(dāng)n充分近似服從自由度為k-r-1的%2分布，其中r是F(x)中被估計(jì)的參數(shù)個(gè)數(shù)。在實(shí)際應(yīng)用中，一般要求np>5，以保證誤差不會(huì)太大?！?2)中心極限定理DeMoivre-Laplace定理：設(shè)隨機(jī)變量門服從參數(shù)為n，p的二項(xiàng)分布，則對(duì)于任意x，有l(wèi)imPn—8門limPn—8門一npnp(1一p<x\=ixexp[-《Idt一8店I2I(4-8)由此可見(jiàn)，二項(xiàng)分布的極限分布是正態(tài)分布。4.2.5卡方檢驗(yàn)設(shè)r,r，…,r是待檢驗(yàn)的一組隨機(jī)數(shù)，假設(shè)H:r,r，…,r為均勻總體的簡(jiǎn)單樣12n012n本。將【0,1］區(qū)間分為m個(gè)小區(qū)間，以(i-1/m,i/m)(=1,2，…,m)表示第i個(gè)小區(qū)間，設(shè){r}i(j=1,2,...,仍落入第i個(gè)小區(qū)間的數(shù)目為n(i=1,2，…,m)。i根據(jù)均勻性假設(shè)，，.落入每個(gè)小區(qū)間的概率為1/m，第i個(gè)小區(qū)間的理論頻數(shù)u――(i=1,2,...,n)統(tǒng)計(jì)量：=m￡ni=1v=￡(ni—四i1旦i=1i漸進(jìn)服從%2(m-1)。給定顯著性水平以，查%2分布表得臨界值后，即可對(duì)經(jīng)驗(yàn)頻率與理論頻率的差異作顯著性檢驗(yàn)(本章卡方檢驗(yàn)中取區(qū)間數(shù)m=500)。=m￡ni=14.2.6柯氏檢驗(yàn)柯氏檢驗(yàn)是連續(xù)分布的擬合性檢驗(yàn)。它檢驗(yàn)樣本的經(jīng)驗(yàn)分布函數(shù)與總體的分布

函數(shù)間的差異u是否顯著。設(shè)隨機(jī)數(shù)為r,r，…,r，從小到大排序后得；,；，…,；。記經(jīng)驗(yàn)分布函數(shù)為F(x)；12n12n〃將F(x)與均勻分布的分布函數(shù)F(x)=x(0<x<1)比較，其最大偏差即柯氏檢驗(yàn)統(tǒng)計(jì)量為:V=max(D+,D-)其中，氣=max1-F(r),1<i<nL」d-=maxnd-=maxn1<i<nf(r)-史in=maxLi-1]nJ利用V2漸進(jìn)地服從柯氏分布這一事實(shí)進(jìn)行顯著檢驗(yàn)。4.2.7序列檢驗(yàn)序列檢驗(yàn)實(shí)際上是用于多維分布的均勻性檢驗(yàn)，它也間接地檢驗(yàn)序列的獨(dú)立性。已知隨機(jī)數(shù)序列｛r｝G=1,2,...,2n)，將容量為2n的隨機(jī)數(shù)一次配對(duì)為：v=(r,r),v二(r,r),...,v=(r,r),、112234n2n-12n如果｛［｝是均勻隨機(jī)數(shù)列，那么它們應(yīng)該構(gòu)成平面上正方形內(nèi)的二維均勻隨機(jī)向量的樣本。將單位正方形分成k2個(gè)燈面積的小正方形，n表示｛v｝(i=1,2,...,n)落入1.,第(i,j)個(gè)小正方形的頻數(shù)，理論頻數(shù)七=n/k2。則檢驗(yàn)統(tǒng)計(jì)量：V=竺左k3ni=1j=1在｛r｝為均勻分布的獨(dú)立抽樣序列成立時(shí)漸進(jìn)地服從x2(k2-1)i將以上二維的序列檢驗(yàn)可以推廣到三維，四維直至一般的d維。即對(duì)〃.｝依次用不相交的d階組合(tuptes):v=(r,r,...,r),TOC\o"1-5"\h\z\o"CurrentDocument"112nv=(r,r,...,r),2d+1d+22d?。?1)d+1'r(k-1)d+2'...'J，它們應(yīng)該是在單位d維超立方體［o,1N中均勻分布的獨(dú)立隨機(jī)樣本。把【0,1］區(qū)間分成m個(gè)相等的小區(qū)間，相應(yīng)地把單位d維超立方體分成md個(gè)小超立方體，用n表示￡｝落入第(j,j,...,j)個(gè)超立方體的個(gè)數(shù)。統(tǒng)計(jì)量：jj2-jlk12kV=也EJE[n-衛(wèi)]23n\jj2…jdmdJj=1jdT漸進(jìn)服從X2(md-1)(nT8)。這種d維均勻分布的檢驗(yàn)(序列檢驗(yàn))間接地檢驗(yàn)了"｝的獨(dú)立性4.3獨(dú)立性檢驗(yàn)獨(dú)立性檢驗(yàn)中常用的方法有:相關(guān)系數(shù)檢驗(yàn)工、相關(guān)系數(shù)檢驗(yàn)工I、列聯(lián)表檢驗(yàn)和游程檢驗(yàn)。4.4對(duì)線性同余法和取小數(shù)法進(jìn)行隨機(jī)性檢驗(yàn)我們?nèi)颖玖縩=1000，分別對(duì)取小數(shù)法和線性同余法進(jìn)行檢驗(yàn)。下面我們就上面所述線性同余法中參數(shù)a，c和m的取值分別采用在36位和32位計(jì)算機(jī)上常用的算法：a=515，c=1，m=231(4-9)a=314115926,c=453806245,m=231(4-10)c=0稱為乘同余法，為了提高乘同余法的可用性，人們進(jìn)行了大量的研究，發(fā)現(xiàn)可通過(guò)恰當(dāng)?shù)倪x擇m及a，可以接近滿洲期，較突出的是素?cái)?shù)取模同余法，下面給出兩個(gè)經(jīng)過(guò)檢驗(yàn)的性能較好的素?cái)?shù)取模同余法，它們是X=52X.1(mod235-31)(4-11)X=75X.1(mod231-1)(4-12)隨機(jī)數(shù)算法檢驗(yàn)表如下：

算法種子樣本均值樣本方差均值檢驗(yàn)方差檢驗(yàn)擬合檢驗(yàn)獨(dú)立性檢驗(yàn)4.2.110.48120.0848-2.060.6315.240.02100.50300.08270.33-0.268.040.811000.49030.0848-1.060.638.64一0.814.2.210.48670.0859-1.461.1119.181.51100.49710.08450.580.519.38-0.151000.50130.08460.740.5512.18-2.364.2.310.49510.0862-0.541.215.28-1.34100.48400.0832-1.76-0.0714.280.351000.50670.08460.740.5512.18-2.364.2.410.49800.0788-0.22-1.917.56-1.36100.49960.0803-0.04-1.316.64-0.731000.49710.0873-0.311.7019.58-0.09取小數(shù)法0.10.49520.0818-0.53-0.6510.68-1.170.20.50970.08201.06-0.5511.32-0.530.30.53470.08543.800.8824.72-0.30取a=0.05,當(dāng)VJ<1.96,通過(guò)均值檢驗(yàn)；當(dāng)IVJ<1.96則通過(guò)方差檢驗(yàn)；當(dāng)|VJ<16.92.則通過(guò)均值檢驗(yàn);當(dāng)|VJ<1.96，則通過(guò)獨(dú)立性檢驗(yàn).上表給出了5個(gè)隨機(jī)數(shù)發(fā)生器其中前4個(gè)均為線性同余法，最后一個(gè)是作者提出的取小數(shù)法。每個(gè)線性同余算法的參數(shù)，都是經(jīng)過(guò)專家精心選出的。由表1可以看到。對(duì)于不同的種子（每個(gè)發(fā)生器各取3個(gè)種子），它們通過(guò)檢驗(yàn)的機(jī)會(huì)基本一致（各有一個(gè)種子通不過(guò)檢驗(yàn)）。我們看到，線性同余法不僅與種子有關(guān)，而且與參數(shù)m,a,c的選取有關(guān)。為了保證其統(tǒng)計(jì)性質(zhì)，一般將m取得很大.這樣，在計(jì)算過(guò)程中，為防止整數(shù)溢出還要進(jìn)行一些算法處理。而取小數(shù)法只與種子的選取以及計(jì)算機(jī)字長(zhǎng)有關(guān)?？梢哉J(rèn)為，取小數(shù)法不失為一種簡(jiǎn)單實(shí)用的隨機(jī)數(shù)發(fā)生器。

第5章新的隨機(jī)數(shù)生成法5.1開方取小數(shù)法在常見(jiàn)的偽隨機(jī)數(shù)產(chǎn)生法中，只要種子取得得當(dāng)，取小數(shù)法仍不失為一種好方法。根據(jù)取小數(shù)法原理，我們將前一次隨機(jī)數(shù)開方后的數(shù)，取其小數(shù)點(diǎn)后第一個(gè)非零數(shù)字后面的尾數(shù)為下一所求隨機(jī)數(shù)。其計(jì)算流程圖如圖1所示。圖1計(jì)算流程圖此方法生成的隨機(jī)數(shù)的好壞，即是否很好的滿足上文提到的重要條件，要進(jìn)行驗(yàn)證。對(duì)于周期問(wèn)題，這種方法同取小數(shù)法，只要不退化，周期可說(shuō)是無(wú)窮的。對(duì)于均勻性和獨(dú)立性要求，下面用統(tǒng)計(jì)學(xué)知識(shí)對(duì)它加以檢驗(yàn)。以下是用開方取小數(shù)法生成的200個(gè)數(shù)，種子為2,我們可以其為樣本進(jìn)行檢驗(yàn)，生成的200個(gè)數(shù)如下。0.4142140.4359420.6025920.762680.7331560.5624540.499690.06890960.6250650.9061030.5189420.2037620.5140010.1693850.1156460.4006810.3299410.7440470.6258160.9108550.5438740.374780.1219290.4918360.0131010.14460.8026360.9589940.792820.904060.50082080.1288730.5898870.6804080.486820.9868030.9337960.6633120.1443970.7999580.9440360.7161490.4625610.8011810.9508730.7512730.6676020.1706890.1314480.6255730.9093170.5358110.3199140.6560930.0999550.16156

0.0194470.3945370.2812160.3029820.5043790.1019630.1931650.3950580.2853620.3419260.8474450.2056750.5351420.315340.615510.8454480.1948220.4138680.4332570.5822270.6303790.9396390.694980.327650.7240720.5092450.136140.6897140.30490.5217770.2234110.7266380.5243080.2409130.9082880.5304150.2829570.3193710.6512940.0702770.6509850.0683650.6146720.8401020.1657060.0706960.6588790.1171330.4224720.4997840.0695440.6371170.9819590.9093840.5361610.3223040.6771850.2291230.7866810.8695020.3247090.6983240.3565770.9714060.8559930.251990.0198640.40940.3984370.3121870.5873680.6639910.1485640.8544040.2434010.9335640.6621120.1370280.7017260.3769080.1392860.7320980.5562730.4583680.7702870.7765970.8124740.0137360.1719970.1472530.8373560.1507180.8822380.3927550.2670140.1673360.0906660.0110850.0528320.2985270.4637580.8099780.9998780.999390.9969470.9847240.9233260.6089880.8037670.9653060.8250.0829490.8800980.3813530.1753820.187860.3342770.7816670.8411920.1716540.1431120.7830110.848790.2129810.6149890.8421220.1767210.2038150.5145870.1734750.1650360.0624650.4992940.0660740.5704840.5530410.4366690.6080960.7980520.9333740.661130.130990.6192550.869273我們先假設(shè)這些數(shù)服從“（0,1）分布，則有:u玉u玉=5=0.500567n2001S2=-—X（u-u）2=0.084274n一1而且有：E（u）=12D（S2）D（S2）=-!180n我們知道服從u（0,1）分布的均值1u=—21，y方^差b2=12取統(tǒng)計(jì)量X，Yu-E（u）X=_=U12n1xDu

YS2—E（S2）當(dāng)n充分大的時(shí)候，則應(yīng)有X1,Y1都近似服從N(0,1)分布。取a=0.05，查正態(tài)分布表Za=1.962由于X1卜YJ=0.178479Y1.960.02777Y1.96由于X1卜YJ=0.178479Y1.96所以在顯著性水平a=0.05條件下，可以接受總體均值u=2，方差a2=1的假設(shè)。12下面再用X2擬合優(yōu)度檢驗(yàn)法對(duì)這些數(shù)作分布均勻性檢驗(yàn)。我們將樣本的取值范圍分布在10個(gè)等寬區(qū)問(wèn)，即分成0~0?1,0?1~0?2,0?2~0?3,0?3~0?4,0?4~0?5,0.5~0.6,0.6~0.7,0.7~0.8,0.8~0.9,0.9~1,10個(gè)區(qū)間統(tǒng)計(jì)實(shí)際落在每個(gè)區(qū)間內(nèi)的樣本個(gè)數(shù)ni如下：i12345678910ni16301520152026171920如對(duì)均勻分布，則這些數(shù)落在第i個(gè)區(qū)間內(nèi)的概率:pi=-10按X2擬合法，取統(tǒng)計(jì)量VV=—^ni2/pi一nnV=—^ni2一n=6.620取a=0.O5,查自由度k-1=10-1=9的X2分布表X205,9=16.92AVI=6.6故應(yīng)接受顯著水平為a=0.05的均勻性假設(shè)。由上面可知這些隨機(jī)數(shù)服從u(0,1)分布。對(duì)于獨(dú)立性，我們可用游程檢驗(yàn)法來(lái)檢驗(yàn)。將這些隨機(jī)數(shù)分別與均值u=0.5相減，取其符號(hào)得到一個(gè)正負(fù)號(hào)序列如下：十十十十4--4-----4-4-4-十十■!■十十十-十十十__4-+-44-+----+-4--4---十十十十--+-++----4-++++-4--4--+4--+-H-++--■4--+4-+--------4-4-4-4-+--4-+統(tǒng)計(jì)其中的正號(hào)個(gè)數(shù)n=104，負(fù)號(hào)個(gè)數(shù)％=96，游程數(shù)「二94假設(shè)這些數(shù)是獨(dú)立分布的，取統(tǒng)計(jì)量r則應(yīng)有E(r)=2nin2+-=100.34

n+n2nn(2nn-n-n)D(r)=心i=49.59(n+n》(n+n-1)r近似于正態(tài)分布。r-E(r)94-100.34nn由于Z—一一———=-0.9rvD(rj、：49.59取a—0.05，查正態(tài)分布表Z—a21.96a|Z|=0.9故應(yīng)接受這一假設(shè)。由上面的檢驗(yàn)可知，種子取2時(shí)，用這種方法生成的隨機(jī)數(shù)比較好。我們可稱這種方法為開方取小數(shù)法，也可當(dāng)作取小數(shù)法的另外一種形式。這種方法優(yōu)于取小數(shù)法的地方在于種了的選取條件要寬松很多，我通過(guò)編制一個(gè)計(jì)算機(jī)程序?qū)υ撍惴ㄟM(jìn)行了模擬，除了完全平方自然數(shù)(如1,4,9,16)以外，大于零的數(shù)大多能當(dāng)作種了使用。顯然，這給用戶提供了方便，這種方法不失為一種好的隨機(jī)數(shù)生成法。歸納起來(lái)，此算法有如下優(yōu)點(diǎn)（1）算法簡(jiǎn)單，除初始值外沒(méi)有其他參數(shù)。（2）序列與初值的取值關(guān)系不大，幾乎可以取得所有非負(fù)有理數(shù)。（3）數(shù)列就具有周期長(zhǎng)，不易退化，統(tǒng)計(jì)性質(zhì)好等優(yōu)點(diǎn)。缺點(diǎn):如何取適當(dāng)?shù)姆N子？5.2一種混合型隨機(jī)數(shù)發(fā)生器20世紀(jì)五、六十年代，隨著計(jì)算機(jī)的發(fā)展，出現(xiàn)了用線性同余法（LCG）和移位寄存器法產(chǎn)生隨機(jī)數(shù)的方法，并一直得到廣泛的應(yīng)用。但是隨著理論與實(shí)踐的深入，這些方法的缺陷及間題的嚴(yán)重性進(jìn)一步暴露，比如線性同余法的稀疏網(wǎng)格，長(zhǎng)周期相關(guān)，周期依賴機(jī)器字長(zhǎng)的缺陷，移位寄存器的稀疏網(wǎng)格，隨機(jī)性依賴于初始值，存在微妙相關(guān)的缺陷。近十余年又出現(xiàn)許多產(chǎn)生隨機(jī)數(shù)的新方法。例如，非線性同余法，特別是其中的逆同余法，進(jìn)位加/借位減/進(jìn)位乘發(fā)生器以及乘子和增量也在遞推中變化的復(fù)合素?cái)?shù)發(fā)生器和各種組合發(fā)生器。然而，單個(gè)發(fā)生器仍存在一些缺陷。與已有的方法不同，用超素?cái)?shù)生成偽隨機(jī)數(shù)的方法和優(yōu)選乘子的超素?cái)?shù)偽隨機(jī)數(shù)法，對(duì)原算法作了改進(jìn)，它的主要思想為:在原有的隨機(jī)數(shù)發(fā)生器的基礎(chǔ)上，利用超素?cái)?shù)的重要性質(zhì)，結(jié)合線性同余發(fā)生器，提出新的組合算法，產(chǎn)生隨機(jī)數(shù)組合發(fā)生器。這種新的隨機(jī)數(shù)生成算法旨在提高隨機(jī)數(shù)的獨(dú)立性。5.2.1超素?cái)?shù)長(zhǎng)周期法不難看出，三種方法（一般超素?cái)?shù)法、優(yōu)選乘子超素?cái)?shù)法以及混合同余法的周期都是2的整數(shù)倍（用2n來(lái)表示）。這種周期有一個(gè)嚴(yán)重缺陷:如果在一個(gè)周期內(nèi)同時(shí)取出相互間隔的兩類隨機(jī)數(shù)a類和b類，在一個(gè)周期有n個(gè)屬于a，n個(gè)屬于b。很明顯a類和b類的數(shù)是不一樣的，而在下一個(gè)周期同樣是重復(fù)上一個(gè)周期，也就是說(shuō)，無(wú)論生成隨機(jī)數(shù)有多少，a類和b類的隨機(jī)數(shù)是不一樣的。比如說(shuō)在1*1的方框內(nèi)作圖，如果生成一個(gè)隨機(jī)數(shù)來(lái)表示x坐標(biāo)，再生成一個(gè)隨機(jī)數(shù)來(lái)表示y坐標(biāo)，那么x和y的取值范圍是不一樣的。比如說(shuō)，周期為10，其中，0，012,014,016,018為一類，011,013,015,017,019為一類，這兩類數(shù)的范圍不一樣，用來(lái)模擬過(guò)程所得到的結(jié)果也是有差異的。這類方法在用于并行計(jì)算等場(chǎng)合時(shí)會(huì)

由于隨機(jī)數(shù)本身產(chǎn)生統(tǒng)計(jì)上的偏差。為避免產(chǎn)生統(tǒng)計(jì)偏差，我們提出改進(jìn)方法，即結(jié)合增量的方法，使增量不是一個(gè)常數(shù)C，而是讓增量每次增加1，相應(yīng)生成隨機(jī)序列的迭代模式為：Z=XZ+C(modM)，C=C+1計(jì)算表明，經(jīng)過(guò)該變換得到的隨機(jī)序列周期為M(M—1)。由于理論分析困難，周期為M(M—1)的結(jié)論尚難于給出嚴(yán)格的證明。但是，本文檢驗(yàn)了小于45016的所有超素?cái)?shù)，周期都為M(M—1)，且如果分成A和B兩類，［0,M一1］范圍的每一個(gè)數(shù)在每一類中出現(xiàn)的次數(shù)都是(M-1)/2,只是在每一類中的排序不一樣。當(dāng)M為45061時(shí)周期己經(jīng)大于2X1。9，足以滿足常規(guī)模擬的需要，故從實(shí)用角度而言上述結(jié)論是成立的。下面以7為例說(shuō)明。選X=上述結(jié)論是成立的。下面以7為例說(shuō)明。選X=10，Z=1，C°T得C1=2,Z1=10x1+2(mod7)=5繼續(xù)下去，得C2=3,Z2=4以此類推所得到的結(jié)果如表1所示。表1不同樣本容量k=5時(shí)的相關(guān)系數(shù)N1020100100010000100000M=9735370.561.702.070.1531.43x10-23.58x10-3M=1048710.962.602.340.1284.51x10-3-3.74x10-3由表1可見(jiàn)，在一個(gè)周期內(nèi)，［O,M-1］的整數(shù)都出現(xiàn)了M—1次，同時(shí)出現(xiàn)的順序更加無(wú)規(guī)律(因不再包含M-1個(gè)數(shù)的片斷反復(fù)重復(fù)，由M個(gè)不同的包含M-1個(gè)數(shù)的片段組成)，把它分成兩類后的結(jié)果如表2和表3所示。表2模數(shù)為1048571時(shí)的優(yōu)選乘子1033130317091081138117771097153117831193154317891217156718611223162120171259166313011697表3以模數(shù)為7的長(zhǎng)周期算法余數(shù)序列542445216112653556320223064660431334105001542445216112653556由表3可見(jiàn)，在A，B兩類中出現(xiàn)O,M-1的所有整數(shù)次數(shù)都為(M—1)/2，在這里就是三次。這樣可避免上面出現(xiàn)的問(wèn)題，即A類和B類出現(xiàn)的數(shù)不一樣。5.2.2組合發(fā)生器的研究在各種各樣的新方法中，組合隨機(jī)數(shù)發(fā)生器是最值得關(guān)注的。組合發(fā)生器是指幾個(gè)不同隨機(jī)數(shù)發(fā)生器組合所得的一類發(fā)生器。例如幾個(gè)線性同余發(fā)生器（LCG）的線性組合或幾個(gè)移位寄存器序列（FRS）的線性組合。原則上說(shuō)，被組合的發(fā)生器可以不限于同一個(gè)類型。但是，不同組合的理論分析是十分困難的。用LCG法產(chǎn)生隨機(jī)數(shù)，有一些缺陷，主要是該方法產(chǎn)生的均勻隨機(jī)數(shù)作為M維均勻隨機(jī)向量時(shí)相關(guān)性大。其次利用超素?cái)?shù)法產(chǎn)生隨機(jī)數(shù)序列均勻性和獨(dú)立性方面不是很理想。為克服LCG法和超素?cái)?shù)法的上述缺陷，得到均勻性和獨(dú)立性更好的隨機(jī)數(shù)，利用組合發(fā)生器所依據(jù)的原則，即打亂數(shù)列的次序使之排列不規(guī)則。先用超素?cái)?shù)長(zhǎng)周期法所產(chǎn)生的隨機(jī)數(shù)序列作為隨機(jī)數(shù)表，再用乘同余發(fā)生器所產(chǎn)生的隨機(jī)數(shù)對(duì)其進(jìn)行重新排列得到的數(shù)列作為新的隨機(jī)數(shù)列，其算法為：用超素?cái)?shù)長(zhǎng)周期法產(chǎn)生L個(gè)隨機(jī)數(shù)，這L個(gè)隨機(jī)數(shù)被順序存放在數(shù)組中；（2）用線性同余發(fā)生器產(chǎn)生一個(gè)隨機(jī)整數(shù)j，要求1-j-L;（3令，然后再用超素?cái)?shù)長(zhǎng)周期法產(chǎn)生一個(gè)隨機(jī)數(shù)y，令\=yo5.2.3隨機(jī)數(shù)算法統(tǒng)計(jì)檢驗(yàn)結(jié)果統(tǒng)計(jì)檢驗(yàn)結(jié)果見(jiàn)下列統(tǒng)計(jì)表格，表中列出了超素?cái)?shù)長(zhǎng)周期法和乘同余發(fā)生器的統(tǒng)計(jì)性質(zhì)，以便比較，其中組合發(fā)生器是由超素?cái)?shù)長(zhǎng)周期法的隨機(jī)數(shù)發(fā)生器和一個(gè)線性同余發(fā)生器利用組合發(fā)生器算法產(chǎn)生的隨機(jī)數(shù)序列。由以下統(tǒng)計(jì)數(shù)據(jù)表4至表6可知，超素?cái)?shù)長(zhǎng)周期法形成的組合發(fā)生器在獨(dú)立性與周期這兩個(gè)特性上都得到了明顯的改善，具有很好的統(tǒng)計(jì)性質(zhì)，可以用作隨機(jī)數(shù)發(fā)生器。表4不同樣本容量下各種方法的均值檢驗(yàn)的統(tǒng)計(jì)值樣本數(shù)1X1021X1031X1041X1051X1061X107超素?cái)?shù)長(zhǎng)周期法0.5040910.4972470.499280.5001880.5002440.500162線性同余法0.5221350.5056620.5006010.49980.5000160.500154組合發(fā)生0.5153240.5151920.4966120.5006710.5002120.500124器表5不同樣本容量下各種方法的均勻性檢驗(yàn)的統(tǒng)計(jì)值樣本數(shù)1X1021X1031X1041X1051X1061X107超素?cái)?shù)長(zhǎng)周期法1411.5214.48414.87430.88035.939線性同余28.413.9210.06415.88419.145723.125法組合發(fā)生14.422.6412.84413.97028.33234.3345器表6幾種隨機(jī)數(shù)發(fā)生器的統(tǒng)計(jì)性質(zhì)比較（N=10000）超素?cái)?shù)長(zhǎng)周期法線性同余法組合發(fā)生器初值111周期2030448660536870912Ta210分組區(qū)間數(shù)202020相距K555一階矩0.499280.5006010.496612二階矩0.3318860.3337870.329965二階中心距0.083017850.08318380.0833523均勻性檢驗(yàn)14.48410.06412.844獨(dú)立性檢驗(yàn)-0.0001490210.000449672-0.000148083我們提出了一種新的隨機(jī)數(shù)發(fā)生器算法，即由超素?cái)?shù)長(zhǎng)周期法和線性同余法利用組合發(fā)生器算法生成新的隨機(jī)數(shù)序列。經(jīng)過(guò)大量數(shù)據(jù)的統(tǒng)計(jì)檢驗(yàn)，新的隨機(jī)數(shù)發(fā)生器算法得出的隨機(jī)數(shù)序列通過(guò)了參數(shù)檢驗(yàn)，均勻性檢驗(yàn)，獨(dú)立性檢驗(yàn)，故可以作為隨機(jī)數(shù)發(fā)生器。組合發(fā)生器的獨(dú)立性較組合前的超素?cái)?shù)長(zhǎng)周期法和線性同余法提高很多。相關(guān)性非常弱，因此在獨(dú)立性上比現(xiàn)有的隨機(jī)數(shù)算法都要優(yōu)越。組合發(fā)生器的均勻性較超素?cái)?shù)長(zhǎng)周期法提高很多。經(jīng)過(guò)組合算法打亂隨機(jī)數(shù)序列后，稀疏網(wǎng)格的現(xiàn)象明顯改善。結(jié)束語(yǔ)隨著計(jì)算機(jī)的飛速發(fā)展，產(chǎn)生隨機(jī)數(shù)的發(fā)生器類型也越來(lái)越多，但是到目前為止人們?cè)絹?lái)越重視組合隨機(jī)數(shù)發(fā)生器的優(yōu)越性。本文就討論了常見(jiàn)的隨機(jī)數(shù)發(fā)生器，并且對(duì)發(fā)生器的優(yōu)劣性進(jìn)行了比較，同時(shí)結(jié)合已有的隨機(jī)數(shù)發(fā)生器的特點(diǎn)提出了一種新的隨機(jī)數(shù)發(fā)生器，也給出了一種特殊（即僅僅給出兩種發(fā)生器的組合）的組合隨機(jī)數(shù)發(fā)生器，并且給出了統(tǒng)計(jì)檢驗(yàn)。參考文獻(xiàn)參考文獻(xiàn)楊自強(qiáng)，魏公毅，綜述:產(chǎn)生隨機(jī)數(shù)的若干新方法.2000.徐鐘濟(jì)，蒙特卡羅方法.上海:上?？萍即髮W(xué)出版社.1985.林國(guó)順，陳佳，一種隨機(jī)教發(fā)生器新算法的研究山大連海事大學(xué)學(xué)報(bào).2005.F.N.DavidandD.E.Barton,CombinatorialChance.NewYork:HafnerPublishingCo.,1962,p230.Tezuka,S.Uniformrandommunbers:theoryandpractice.Nowell,Mass;KluwerAcademicPublishers,1955.張?jiān)?，隨機(jī)數(shù)發(fā)生器和隨機(jī)數(shù)性能檢驗(yàn)方法研究，電子科技大學(xué)碩士學(xué)位論文2006.張廣強(qiáng)，均勻隨機(jī)數(shù)發(fā)生器的研究和統(tǒng)計(jì)檢驗(yàn)，大連理工大學(xué)碩士學(xué)位論文2005.楊自強(qiáng),魏公毅，常見(jiàn)隨機(jī)數(shù)發(fā)生器的缺陷及組合隨機(jī)數(shù)發(fā)生器的理論與實(shí)踐.2001致謝值此論文完成之際，首先感謝我的導(dǎo)師段勇。在段老師的耐心指導(dǎo)下我才能夠完成這篇論文.段老師讓我領(lǐng)略到微分方程數(shù)值解這門學(xué)科的魅力，激發(fā)了我對(duì)這一領(lǐng)域的興趣，增加了我對(duì)這領(lǐng)域的向往。在此，謹(jǐn)向我的指導(dǎo)老師致以最崇高的敬意和忠心的感謝。其次我還要感謝電子科技大學(xué)給我提供了一個(gè)團(tuán)結(jié)，友好，平和的環(huán)境，讓我能夠在這樣和諧而且積極的環(huán)境學(xué)習(xí)。我還要感謝應(yīng)數(shù)一班的所有同學(xué)，謝謝你們四年來(lái)的支持和鼓勵(lì)。最后我要謝謝我的父母這二十多年來(lái)對(duì)我生活學(xué)習(xí)上的關(guān)心和支持。外文資料原文ParallelRandomNumberGeneration:Long-