《混合同余法產(chǎn)生均勻分布隨機(jī)數(shù)產(chǎn)生方法總結(jié)》由會員分享，可在線閱讀，更多相關(guān)《混合同余法產(chǎn)生均勻分布隨機(jī)數(shù)產(chǎn)生方法總結(jié)（5頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、混合同余法產(chǎn)生均勻分布隨機(jī)數(shù)產(chǎn)生方法 總結(jié) 主要學(xué)習(xí)混合同余法產(chǎn)生各種分布的隨機(jī)數(shù)的方法，見參考文獻(xiàn) ［1, 2］，重點 參考［2］。其中要注意混合同余法產(chǎn)生隨機(jī)數(shù)的參數(shù)的選取。 1混合同余法產(chǎn)生均勻分布的隨機(jī)數(shù) 1.1混合同余法 通過同余運(yùn)算生成偽隨機(jī)數(shù)的方法稱為同余法，常用的同余法包括加同余法、 乘同余法、混合同余法、除同余法。其中乘同余法和混合同余法的性能更好，有 速度快、內(nèi)存省、周期長、統(tǒng)計特性好等優(yōu)點。混合同余法是 Lehmer在1951 年提出的，其迭代公式為 ⑵： Xn =mod(AXn-1 +C, M) (1.1) (1.2) Yn=Xn/M

2、公式(1.1)、(1.2)中，mod表示求余函數(shù)，A,C, M均為正整數(shù)。其中M是模 數(shù)，A是乘數(shù)，C是增量，Xo為初始值(0空X。乞M)，當(dāng)C=0時，稱此算法為 乘同余法；若C = 0，則稱算法為混合同余法，當(dāng)C取不為零的適當(dāng)數(shù)值時，有 一些優(yōu)點，但優(yōu)點并不突出，故常取 C=0。Xn是在(0, M )內(nèi)服從均勻分布的隨 機(jī)變量，Y,則是在(0, 1)內(nèi)服從均勻分布的隨機(jī)變量。式中X。, A,C, M的取值并 不是隨意的，模M大小是發(fā)生器周期長短的主要標(biāo)志，常見有 M為素數(shù)，取A 為M的原根，則周期T=M -1。試驗統(tǒng)計表明，用以下參數(shù)進(jìn)行混合同余法產(chǎn)生 的隨機(jī)序列的統(tǒng)計特性較好： Xn=m

3、od(314159269X n-1+453806245,231) (1.3) (1.4) Xn=mod(515Xn-1+1,235) 7 35 Xn=mod(2 Xn-1+1, 2 ) (1.5) Xn二mod(2045X n-1+1, 220) (1.6) 10 7 Xn=mod(7X n-1,10 ),Xo=1,T=5 10 (1.7) Xn=mod(5 13Xn-1,236),X 0 = 1,T=23^ 2 1010 (1.8) Xn=mod(5 17Xn-1,212),Xo = 1,T=2 40 1012 (1.9) 31 Xn=mod(32719X n-1, 2

4、 -1), X。任意 (1.10) 31 Xn=mod(16807X n-1, 2 -1), X0任意 (1.11) 31 Xn=mod(1220703125X n-1, 2 -1),X0任意 (1.12) 15 Xn=mod(9869X n-1 +6925, 2 -1) (1.13) 31 31 在式(1.10)~(1.12)中 T =2 -2 , 16807、32719、1220703125 都是 2 -1 的原根。 混合同余法產(chǎn)生的隨機(jī)序列具有以下特點： Xn重復(fù)周期較小，由于Xn取值在(0, M )內(nèi)，其周期TEM ,T受X°,A,C,M 的值得影響，在

5、編程實現(xiàn)時，浮點運(yùn)算也會對 T產(chǎn)生影響 用此方法產(chǎn)生的隨機(jī)序列，在一個周期內(nèi)任意兩個隨機(jī)數(shù)不可能相等，這往 往與實際情況不相符 經(jīng)Hull和Dobell證明，只有X0,A,C,M滿足以下一些關(guān)系才能實現(xiàn)周期最 大化，即T=M，條件如下： C與M互質(zhì)(或互素，即它們的最大公約數(shù)為 1) 設(shè)q為某一質(zhì)數(shù)，M分別能被q和4整除，且(A-1 )能被q和4整除 產(chǎn)生具有最大周期的偽隨機(jī)序列的混合同余法算法為： k Xn =mod((4a+1)Xn-1 (2c+1), 2 ) (1.14) Yn=Xn/2k (1.15) k 由于M=2 ,k-2時，M只有一個素數(shù)因子 2，且4也是M

6、的因子，此時 A=4a+1， 正好滿足了 T=M的第二個條件；而此時C=2c+1剛好與M互質(zhì)，即滿足T = M的 第一個條件 1.2改進(jìn)的混合同余法 改進(jìn)的混合同余法的迭代公式如下⑵： Xn =mod(AXn-i n, M) (1.16) Yn=Xn/M (1.17) 改進(jìn)的混合同余法具有以下特點： 比混合同余法產(chǎn)生的周期長， T _M 允許某個偽隨機(jī)數(shù)重復(fù)發(fā)生，且重復(fù)發(fā)生的次數(shù)為 [T / M ] 偽隨機(jī)序列的周期T一般與初始值Xo的選取無關(guān)，只有極個別的情況除外 1.3原根相關(guān)知識 1.3.1歐拉函數(shù) 在數(shù)論，對正整數(shù)n,歐拉函數(shù)是少于或等于n的數(shù)中與n互質(zhì)的數(shù)的

7、數(shù)目。 此函數(shù)以其首名研究者歐拉命名，它又稱為 Euler's totient function、©函數(shù)、歐 拉商數(shù)等。例如© (8)=4因為1,3,5,7均和8互質(zhì)。 1.3.2原根 定義1 設(shè)m > 1，(a, m) = 1，則使 r a 三 1(mod m) (1.18) 成立的最小的正整數(shù)r，稱為a對模m的指數(shù)，記為m(a)，在不致誤會的情況下， 簡記為(a)0 由Euler定理，當(dāng)r = (m)時式(1)成立，因此，恒有 m(a) ? (m)。 若 a 三 b (mod m)，(a, m) = 1，則顯然有 亦(a) = 6m(b)。

8、 定義2 若、m(a) = (m)，則稱a是模m的原根。 例如，當(dāng)m = 7時，因為 12 3 21 三 2，22三 4，23三 1 (mod 7)， 所以、7(2) = 3。又因為 1 2 3 4 5 6 31 三 3, 32三 2, 33三 6, 34三 4, 35三 5, 36三 1 (mod 7), 所以刀(3) = 6 = (7), 3是模7的原根。 以后，在談到a對模m的指數(shù)時，總假定m > 1, (a, m)= 參考文獻(xiàn) [1] 吳飛.產(chǎn)生隨機(jī)數(shù)的幾種方法及其應(yīng)用 [J].數(shù)值計算與計算機(jī)應(yīng)用 [2] 郭鳳鳴.一種生成大周期偽隨機(jī)數(shù)的新算法一一改進(jìn)的混合同余法 1。 ,2006, (01): 48-51. [J].地球科學(xué),1992, (06): 733-738.