偽隨機(jī)數(shù)的產(chǎn)生及其性能評(píng)價(jià)

1、偽隨機(jī)數(shù)的產(chǎn)生及其性能評(píng)價(jià)偽隨機(jī)數(shù)的產(chǎn)生及其性能評(píng)價(jià)吳軍1呂敏2雷金娥3（1.重慶大學(xué)光電工程學(xué)院，重慶4000301；2.中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，合肥230026；3.南昌工程學(xué)院計(jì)算機(jī)系，南昌330099）摘要：摘要：系統(tǒng)仿真或加密算法中常需要產(chǎn)生滿(mǎn)足一定分布函數(shù)的偽隨機(jī)數(shù)，高級(jí)程序設(shè)計(jì)語(yǔ)言中的庫(kù)函數(shù)采用線性同余法產(chǎn)生一個(gè)在[032767]服從均勻分布的偽隨機(jī)數(shù)，但每次程序運(yùn)行的結(jié)果都是相同的，利用當(dāng)前系統(tǒng)時(shí)間和數(shù)學(xué)方法可以產(chǎn)生

2、滿(mǎn)足各種分布要求的偽隨機(jī)數(shù)。以CC為例，采用概率統(tǒng)計(jì)的方法檢驗(yàn)了產(chǎn)生的偽隨機(jī)數(shù)是否符合給定分布函數(shù)的要求，并且其隨機(jī)性、均勻性等統(tǒng)計(jì)特性是否滿(mǎn)足實(shí)際應(yīng)用的需要。關(guān)鍵字：關(guān)鍵字：偽隨機(jī)數(shù)CC統(tǒng)計(jì)檢驗(yàn)；均勻分布；正態(tài)分布；指數(shù)分布中圖分類(lèi)號(hào)：中圖分類(lèi)號(hào)：TP文獻(xiàn)標(biāo)識(shí)碼：文獻(xiàn)標(biāo)識(shí)碼：1、引言、引言在計(jì)算機(jī)仿真和模擬、密碼學(xué)等應(yīng)用中，常需要產(chǎn)生一些隨機(jī)數(shù)，自然界中存在大量的隨機(jī)現(xiàn)象，但在計(jì)算機(jī)中，只能產(chǎn)生滿(mǎn)足一定要求的偽隨機(jī)數(shù)來(lái)模擬真實(shí)世界中的

3、隨機(jī)現(xiàn)象。產(chǎn)生偽隨機(jī)數(shù)的方法有硬件方法和軟件方法，硬件方法可以在計(jì)算機(jī)上附上一個(gè)硬設(shè)備或者采用移位寄存器來(lái)產(chǎn)生偽隨機(jī)數(shù)；軟件方法一般都采用數(shù)學(xué)公式法。近年來(lái)在計(jì)算機(jī)中，比較廣泛使用的方法就是同余法，而在高級(jí)程序設(shè)計(jì)語(yǔ)言中常采用線性同余法[8]。每次生成的偽隨機(jī)數(shù)需要滿(mǎn)足獨(dú)立的條件及給定分布函數(shù)的要求，但高級(jí)程序設(shè)計(jì)語(yǔ)言中提供的庫(kù)函數(shù)產(chǎn)生的偽隨機(jī)數(shù)都是滿(mǎn)足一定條件的均勻分布隨機(jī)數(shù)，且在同一次程序運(yùn)行中，每次產(chǎn)生的偽隨機(jī)數(shù)是完全相同的，本文

4、將介紹利用一些數(shù)學(xué)變換方法產(chǎn)生在任意區(qū)間內(nèi)服從任意分布的偽隨機(jī)數(shù)，并進(jìn)行統(tǒng)計(jì)檢驗(yàn)以檢查其是否能滿(mǎn)足要求。文獻(xiàn)[14]提出了一種比較好的尾數(shù)和檢驗(yàn)法，但比較復(fù)雜，本文采用較為簡(jiǎn)單的頻率統(tǒng)計(jì)法。2、R函數(shù)和線性同余算法函數(shù)和線性同余算法C語(yǔ)言中提供的r()函數(shù)可以產(chǎn)生一個(gè)從0到32767服從均勻分布的正整數(shù)，r()函數(shù)即采用了線性同余算法。該算法如下：取足夠大的正整數(shù)m（一般取計(jì)算機(jī)精度范圍內(nèi)能夠表示的最大整數(shù)）和任意的自然數(shù)a，X0，b。

5、其中i＝1、2、3……，mod表示取余。（1）mbaXXiimod)(1???（1）式中a為乘子，X0為種子，b為常數(shù)，m為模。線性同余法是一種遞歸算法，即先提供一個(gè)種子X(jué)0，逐次遞歸即得到一個(gè)不超過(guò)模m的整數(shù)數(shù)列?？梢钥闯鲇纱水a(chǎn)生的數(shù)列并不是真正的隨機(jī)數(shù)，但是提供一個(gè)隨機(jī)的種子，產(chǎn)生的數(shù)列在0～m循環(huán)，如果產(chǎn)生大量的整數(shù)密集分布在[0，m]上，就可以近似認(rèn)為服從[0，m]上的均勻分布。把數(shù)列除以m，就得到服從[0，1]上的均勻分布。3

6、、偽隨機(jī)數(shù)性能評(píng)價(jià)的基本原理、偽隨機(jī)數(shù)性能評(píng)價(jià)的基本原理隨機(jī)性和均勻性檢驗(yàn)采用頻率統(tǒng)計(jì)檢驗(yàn)法，該算法原理如下：收稿日期：收稿日期：200941基金項(xiàng)目：基金項(xiàng)目：南昌工程學(xué)院青年基金科技項(xiàng)目(2006KJ029)作者簡(jiǎn)介：作者簡(jiǎn)介：吳軍（1977），男，四川達(dá)州人，在讀博士，主要從事嵌入式和操作系統(tǒng)方面的研究。Email:wj2135187@，手機(jī)：13668013619通訊作者：通訊作者：吳軍，wj2135187@選法的效率。③組合法

7、：如果需要生成的偽隨機(jī)數(shù)服從分布函數(shù)F(x)，F(xiàn)(x)可以用其他更簡(jiǎn)單的分布函數(shù)F1，F(xiàn)2，…，F(xiàn)m的凸組合表達(dá)時(shí)，即假定對(duì)所有的x，，其中???miiixFpxF1)()(pi≥0，。則可以先產(chǎn)生服從Fi的m個(gè)隨機(jī)數(shù)數(shù)列，然后再利用這些隨機(jī)數(shù)數(shù)列11???miip的組合得到服從F(x)分布的偽隨機(jī)數(shù)。④經(jīng)驗(yàn)分布法：主要用于產(chǎn)生離散分布的隨機(jī)數(shù)?，F(xiàn)實(shí)中很多隨機(jī)現(xiàn)象的理論分布往往無(wú)法確切得出，但可以根據(jù)它們的經(jīng)驗(yàn)公式來(lái)模擬抽樣。⑤近似法：

8、對(duì)于分布函數(shù)比較復(fù)雜，難以對(duì)其求解的情況下，可以利用一些定理或公式來(lái)近似產(chǎn)生偽隨機(jī)數(shù)。比如正態(tài)分布的分布函數(shù)比較復(fù)雜，對(duì)其求反函數(shù)也比較困難，則可以利用中心極限定理來(lái)近似得出服從正態(tài)分布的偽隨機(jī)數(shù)。5、各種偽隨機(jī)數(shù)的生成方法及其評(píng)價(jià)、各種偽隨機(jī)數(shù)的生成方法及其評(píng)價(jià)①均勻分布偽隨機(jī)數(shù)的產(chǎn)生：設(shè)r_MAX＝32767、dR＝r()r_MAX，則dR就是一個(gè)滿(mǎn)足[0，1]均勻分布的偽隨機(jī)數(shù)，其中r()函數(shù)是CC中的庫(kù)函數(shù)，r_MAX是16位字

9、長(zhǎng)計(jì)算機(jī)中int型變量能夠表示的最大正整數(shù)。如果要產(chǎn)生[a，b]上均勻分布的偽隨機(jī)數(shù)，可以采用適當(dāng)?shù)木€性變換。文獻(xiàn)[13]中為了提高隨機(jī)性，采用了平方的方法，可以證明均勻分布的變量平方后不再服從均勻分布，頻率直方圖也出現(xiàn)了較大的跳躍，所以不能滿(mǎn)足要求。CC中可以用如下的代碼來(lái)實(shí)現(xiàn)任意區(qū)間[a，b]上均勻分布的偽隨機(jī)數(shù)。產(chǎn)生[a，b]上均勻分布的偽隨機(jī)數(shù)可以用如下的偽代碼來(lái)實(shí)現(xiàn)：voidEquR(doubledRan，doublea，do

10、ubleb)unsignedintseedValstructtimebtimeBufftime(seedVal=((((unsignedint)timeBuf.timesr((unsignedint)seedVal)f(i=0inum_MAXi)dTemp=(double)r()r_MAX(dRani)=dTemp(ab)bCC中需要提供一個(gè)種子給r()函數(shù)，該算法中用系統(tǒng)當(dāng)前時(shí)間來(lái)作種子，以保證每次得到的偽隨機(jī)數(shù)都不同，即各次產(chǎn)生的偽