伪随机数的产生及其性能评价.doc

伪随机数的产生及其性能评价吴 军1 吕敏2 雷金娥3（1.重庆大学光电工程学院，重庆 400030收稿日期：2009-4-1基金项目：南昌工程学院青年基金科技项目 (2006KJ029)作者简介：吴 军（1977-），男，四川达州人，在读博士，主要从事嵌入式和操作系统方面的研究。Email: ，手机通讯作者：吴 军，；2.中国科学技术大学计算机学院，合肥 230026；3.南昌工程学院计算机系，南昌 330099）摘要：系统仿真或加密算法中常需要产生满足一定分布函数的伪随机数，高级程序设计语言中的库函数采用线性同余法产生一个在0,32767 服从均匀分布的伪随机数，但每次程序运行的结果都是相同的，利用当前系统时间和数学方法可以产生满足各种分布要求的伪随机数。以C/C+为例，采用概率统计的方法检验了产生的伪随机数是否符合给定分布函数的要求，并且其随机性、均匀性等统计特性是否满足实际应用的需要。关键字： 伪随机数 C/C+ 统计检验；均匀分布；正态分布；指数分布中图分类号：TP 文献标识码：1、引言在计算机仿真和模拟、密码学等应用中，常需要产生一些随机数，自然界中存在大量的随机现象，但在计算机中，只能产生满足一定要求的伪随机数来模拟真实世界中的随机现象。产生伪随机数的方法有硬件方法和软件方法，硬件方法可以在计算机上附上一个硬设备或者采用移位寄存器来产生伪随机数；软件方法一般都采用数学公式法。近年来在计算机中，比较广泛使用的方法就是同余法，而在高级程序设计语言中常采用线性同余法8。每次生成的伪随机数需要满足独立的条件及给定分布函数的要求，但高级程序设计语言中提供的库函数产生的伪随机数都是满足一定条件的均匀分布随机数，且在同一次程序运行中，每次产生的伪随机数是完全相同的，本文将介绍利用一些数学变换方法产生在任意区间内服从任意分布的伪随机数，并进行统计检验以检查其是否能满足要求。文献14提出了一种比较好的尾数和检验法，但比较复杂，本文采用较为简单的频率统计法。2、Rand函数和线性同余算法C语言中提供的rand( )函数可以产生一个从0到32767服从均匀分布的正整数，rand( )函数即采用了线性同余算法。该算法如下：取足够大的正整数m（一般取计算机精度范围内能够表示的最大整数）和任意的自然数a，X0，b。其中i1、2、3，mod表示取余。 （1）（1）式中a为乘子，X0为种子，b为常数，m为模。线性同余法是一种递归算法，即先提供一个种子X0，逐次递归即得到一个不超过模m的整数数列。可以看出由此产生的数列并不是真正的随机数，但是提供一个随机的种子，产生的数列在0m循环，如果产生大量的整数密集分布在0，m上，就可以近似认为服从0，m上的均匀分布。把数列除以m，就得到服从0，1上的均匀分布。3、伪随机数性能评价的基本原理随机性和均匀性检验采用频率统计检验法，该算法原理如下：假设x服从U0，1（U表示均匀分布），把0，1等分成n个小区间。以表示第i个小区间，如果ri是0，1上均匀分布随机变量x的一个抽样值，则它落在任一个小区间的概率为1/n，故N个抽样值落在任一小区间的理论频数，设实际频数ni为第i个小区间实际测到的频数，则构造统计量。 （2）由皮尔逊定理可知，渐进服从分布（）。若取置信度为，查分布表得到，若，则认为这批随机数在统计性能上1可信，否则拒绝。对一次产生的N个伪随机数的独立性检验可以使用相关系数检验法，即若两个随机变量独立，则其相关系数为零，反之则不然。即相关系数为零是随机变量独立的必要条件，但可以通过相关系数的大小来判定其线性相关性的强弱。N个随机变量r1，r2，rN中相距为j的两个随机样本的相关系数为： （3）其中j1，2，3，。若ri之间相互独立且N充分大（如Nj50）时，则统计量 （4）渐进地服从标准正态分布N(0,1)。由C/C+中伪随机数的生成算法可知，C/C+生成的伪随机数是递推生成的，所以各伪随机数之间并不独立，但可以通过检验其相关性，满足一定要求便近似认为它们是线性无关的。4、任意分布伪随机数的生成C/C+本身只能生成032767之间均匀的随机整数，通过线性变换可以产生任意区间内均匀分布的随机浮点数。如果要生成满足任意分布的伪随机数，一般有以下五种方法：求逆法：任意分布的随机变量X的分布函数F(x)服从U(0,1)分布，而F(x)的反函数F1(x)和X具有相同的分布。所以可以先获得一个0,1上的均匀分布随机变量Y，则XF1(Y)具有给定的分布密度函数。舍选法：舍选法适用于任意分布密度函数有界的情况。设某一随机变量的密度函数f(x)满足 （5）舍选法先生成一个a,b上均匀分布的伪随机数，每生成一个伪随机数先判断该点是否落在f(x)曲线的下方或曲线上，满足条件则保留该数，否则舍去。由此可以看出舍选法不是每次都能得到一个伪随机数，平均每1/M(ba)次得到一个符合判别准则的数，称之为舍选法的效率。组合法：如果需要生成的伪随机数服从分布函数F(x)，F(x)可以用其他更简单的分布函数F1，F2，Fm的凸组合表达时，即假定对所有的x，其中pi0，。则可以先产生服从Fi的m个随机数数列，然后再利用这些随机数数列的组合得到服从F(x)分布的伪随机数。经验分布法：主要用于产生离散分布的随机数。现实中很多随机现象的理论分布往往无法确切得出，但可以根据它们的经验公式来模拟抽样。近似法：对于分布函数比较复杂，难以对其求解的情况下，可以利用一些定理或公式来近似产生伪随机数。比如正态分布的分布函数比较复杂，对其求反函数也比较困难，则可以利用中心极限定理来近似得出服从正态分布的伪随机数。5、各种伪随机数的生成方法及其评价均匀分布伪随机数的产生：设rand_MAX32767、dRandrand( )/rand_MAX，则dRand就是一个满足0，1均匀分布的伪随机数，其中rand( )函数是C/C+中的库函数，rand_MAX是16位字长计算机中int型变量能够表示的最大正整数。如果要产生a，b上均匀分布的伪随机数，可以采用适当的线性变换。文献13中为了提高随机性，采用了平方的方法，可以证明均匀分布的变量平方后不再服从均匀分布，频率直方图也出现了较大的跳跃，所以不能满足要求。C/C+中可以用如下的代码来实现任意区间a，b上均匀分布的伪随机数。产生a，b上均匀分布的伪随机数可以用如下的伪代码来实现：void EquRand(double* dRan，double a，double b)unsigned int seedVal; struct timeb timeBuf; ftime(&timeBuf); seedVal=(unsigned int)timeBuf.time&0xFFFF)+ (unsigned int)timeBlitm) (unsigned int)timeBlitm); srand(unsigned int)seedVal); for(i = 0; i num_MAX; i+) dTemp = (double)rand() / rand_MAX; *(dRan+i) = dTemp * ( a - b ) - b; C/C+中需要提供一个种子给rand( )函数，该算法中用系统当前时间来作种子，以保证每次得到的伪随机数都不同，即各次产生的伪随机数相互之间独立。生成1000个伪随机数，作出频率统计图如图1。作频率统计图时，需要去掉最大值和最小值，把中间所有的伪随机数分成若干个区间，由统计学的方法，区间数和伪随机数的总个数需要保证一定的关系。图1中的点表示在该区间内伪随机数出现的频率值，可以看出，如果把点拟合成曲线，基本上符合均匀分布的函数曲线图。图1 100，100上均匀分布的伪随机数0,1上均匀分布的伪随机数的统计检验：均匀性和随机性检验：把0,1均分成10个小区间，生成1000个0,1上均匀分布的伪随机数，统计每个小区间上的实际频数并由式（2）计算出统计量，计算10次并取最大值14.16000。取置信度5，查分布表得到16.919，显然。所以这1000个伪随机数服从0,1上均匀分布是95可信的，可以看出C/C+中生成的伪随机数的随机性和均匀性的可信度是很高的。独立性检验：假设取j为1、10、20和100，由式（4）分别计算出其统计量uj为0.003420、0.031507、0.005547和0.000510。查标准正态分布表得(0.95)1.64，由此可知，C/C+中生成的均匀分布伪随机数的独立性是满足95可信度的。求出生成的1000个均匀分布的伪随机数的样本平均值和样本方差，因为它们分别是给定分布的期望和方差的无偏估计。用程序算出的样本均值为0.975018，样本方差为57.898914。-100,100上均匀分布的期望和方差分别为0和57.735027，可以看出误差都在+%5以内。因此，采用当前系统时间作为种子提供给rand( )函数，采用适当的线性变换生成的a，b上的均匀分布的伪随机数可以满足实际应用需要。正态分布伪随机数的生成：正态分布的分布函数比较复杂，其反函数也无法用解析的方式来表达，所以无法用求反函数的方法来生成正态分布的伪随机数，一般可以用以下两种方法。第一种是由瑞利分布导出的公式，若x1、x2是0,1上的均匀分布则y1=(-2*ln(x1)0.5*cos(2*pi*x2)，y2=(-2*ln(x2)0.5*sin(2*pi*x1)是标准正态分布的随机数。第二种是近似法生成，由中心极限定理可知独立同分布的多个随机变量和的分布趋近于正态分布。取k个在0,1均匀分布的随机变量x1,x2,.,xk，则它们的和近似服从正态分布。实践中，一般取k=12，（因为D(xi)=1/12），则新的随机变量yx1x2.x126可以满足一般精度下的N(0,1)分布的要求（因 E(y)=0，D(y)=12*1/121）。以上两种方法本质都是采用数学公司的近似法。有了标准正态分布的伪随机数，就可以用线性变换的方法获得服从任意正态分布的伪随机数。图2是用第二种方法生成的服从N(0,502)分布的伪随机数。图2 正态分布N(0,502)的伪随机数指数分布伪随机数的生成：指数分布的分布函数的反函数容易求出，指数分布的分布函数如式（6）。 （6）求式（6）的反函数可得，设U服从0,1的均匀分布，则即为所求的随机数，又因均匀分布随机变量的线性变换仍服从均匀分布，所以1u服从0,1上的均匀分布。由此可得 （7）式（7）即为所求的服从指数分布的随机数。由式（7）生成的伪随机数的频率统计图如图3所示。图3 参数0.01的指数分布的伪随机数由于正态分布和指数分布都是以均匀分布为基础采用数学方法生成的，所以不再进行统计检验。6、结论实验中分别生成了1000个服从均匀分布、正态分布和指数分布的伪随机数，对均匀分布作了随机性、均匀性和独立性统计检验，满足95的可信度要求。分别求出各分布的伪随机数的平均值和样本方差，与给定分布的期望和方差的误差都小于5。由此可得出结论：C/C+中生成的伪随机数满足精度要求，可在实践中应用如建模和仿真等等。参考文献：1.胡性本，刘向明，方积乾.非均匀分布随机数的产生及其在计算机模拟研究中的应用.数理医药学杂志.2003年，第13卷第1期：5960；2.王瑞胡.计算机中伪随机数生成及其在VISUAL C+中的实现.计算机与信息技术. 2005年，第09期：7580；3.肖力.利用PASCAL语言产生伪随机数方法简探.鄂州大学学报.1996年，第4期：1720；4.杨振海，张国志. 随机数生成.数理统计与管理.2006年，第25卷第2期：244252；5.马华，张晓清，张鹏鸽. 一种基于线性同余算法的伪随机数产生器.纯粹数学与应用数学.2005年，第21卷第3期：206209；6.王萍，许海洋. 一种新的随机数组合发生器的研究.计算机技术与发展.2006年，第16卷第4期：7981；7.易同贸. 正态分布的模拟及实现.长江职工大学学报.2003年，第20卷第3期：2526；8.王红卫.建模与仿真.北京：科学出版社，2002年；9.谭浩强.C程序设计（第二版）.北京：清华大学出版社，1999年；10. 欧俊豪，王家生，徐漪萍等. 应用概率统计（第二版）.天津：天津大学出版社，1999年；11. Newsuppy.标准库rand()函数的缺陷以及Blitz+随机数生成的简介. /newsuppy/archive/2004/09/15/104848.aspx；12. EmilMatthew.随机数产生原理及应用. /EmilMatthew/archive/2006/04/21/672276.aspx；13.戎亚新.任意分布的随机数的产生方法VC程序实现方法. /Document/ProDev/arithmetic/200508294092.htm.14.时正华，袁永生. 伪随机数随机性的一种新检验.河海大学学报自然科学版.2005年，第33卷第2期：232236；15.张传林，林立东.伪-随机数发生器及其应用.数值计算与计算机应用.2002年，第3期：188208；Generating of Pseudo Random Number and Evaluating of The Performance In C/C+WuJun1Abstract：In the program of systematic imitation and encrypt, we often need some Pseudo Random Number which meet a certain distribution, In advanced programming language, library function take linear congruence to produce one Pseudo Random Num