伪随机数的生成

1、 摘摘 要要 在计算机上用数学的方法产生随机数列是目前通 用的方法，它的特点是占用的内存少，速度快用数 学方法产生的随机数列是根据确定的算法推算出来的， 严格说来并不是随机的，因此一般称用数学方法产生 的随机数列为伪随机数列不过只要用数学公式产生 出来的伪随机数列通过统计检验符合一些统计要求， 如均匀性、抽样的随机性等，也就是说只要具有真正 随机数列的一些统计特征，就可以把伪随机数列当作 真正的随机数列使用 . 由于是用算法产生的，因而本质上是决定性的， 再加上计算机字长有限，所以无论用什么算法产生的 数列，在统计特征上都不可能完全与从均匀分布中抽 样所得的子样完全相同，因而只能要求尽可能地近

2、 似 这种在计算机上用算法得到的统计性质上近似于0，1 上均匀分布的数，一般就称为伪随机数，以区别于真 正从0，1上均匀分布中抽样所得到的随机数为了快 速产生统计特征良好的伪随机数，数学上一般采用递 推公式 Xn+1= f(Xn,Xn-1 ， ，Xn-k) 在给定一组初值X0，X-1,X-2, ，X-k 后，即可逐步求 出X1，X2,X3 在此基础上产生随机数 摘摘 要要 随机数的产生随机数的产生 一随机数的概念一随机数的概念 对随机系统进行模拟，需要产生服从某种分布的一对随机系统进行模拟，需要产生服从某种分布的一 系列系列随机数随机数. 定义定义：设随机变量：设随机变量X（总体）服从某种随机

3、分布，对其（总体）服从某种随机分布，对其 进行了进行了n次独立观察次独立观察, ,得到一组得到一组简单随机样本简单随机样本 X1，X2， Xn ,满足：满足： 1） X1，X2，Xn相互独立；相互独立； 2）每一个）每一个X1，X2，Xn都与总体都与总体X 同分布同分布. . 利用某种方法得到一串利用某种方法得到一串数列数列r1 , r2 , , rn 一、伪随机数生成算法伪随机数生成算法 1.1取中法 1.2移位法 1.3同余法 11 取中法 产生伪随机数列最早的方法是平方取中法，即将一个2s位十进 制随机数平方后得到的一个4 s位数，去头截尾取中间2s 位数作 为一个新的随机数，重复上述过

4、程便得到一伪随机数列平方 取中法的递推公式： Xn+1=-X2n10 s (mod 102s )， (1) 产生伪随机数列: Rn=Xn/102s=Xn10-2s (2) 平方取中法的优点为在计算机上易于实现，内存占用少，但仍 存在对小数目偏倚的现象，均匀性不好，数列的长度和周期难 以确定，对初始数据的依赖很大 11 取中法 对平方取中法进行改进，产生了乘积取中法，如果要产生具有 10进制2s位的伪随机数列，任取两个初始随机数X0,X1，用递推 公式: Xn+2=Xn+1Xn10s (mod 102s ) (3) 产生伪随机数列 Rn =Xn10-2s (4) 乘积取中法与平方取中法比较，从产

5、生的伪随机数列长度及均 匀性方面都有改善，但是数列长度还是不够，而且对初始值的 依赖性很大 12 移位法 电子计算机善于进行移位等逻辑运算，应用机器的这个特点有 一类产生伪随机数列的方法，该方法称为移位法 如果字长为32位的计算机，取一初始值X0，将X0左移7位得X01， 右移7位得,X02.将X01和 X02进行指令相加得到X1 ，再对X1 进 行上述运算过程得到X2，这样多次重复可得正整数序列Xn，取 Rn=Xn2-32为0，1上均匀分布的伪随机数列通项 12 移位法 这一算法 递推公式为:Xn+l= Xn 2 7 +Xn 2 -7 (mod2-32) ， 产生伪随机数列 Rn+1=Xn+

6、1 2-32(5) 移位法运算速度快，但是对初始值的依赖性也很大，一般地初 始值不能取得太小，选得不好会使伪随机数列长度较短 13 同余法 目前产生伪随机数列比较好的方法为同余法，其中有混合同余目前产生伪随机数列比较好的方法为同余法，其中有混合同余 法、加同余法和乘同余法、加同余法和乘同余 法法 采用线性递推公式采用线性递推公式: Xn+1=Xn + C (mod M )，0 Xn+1 M ， 产生伪随机数列产生伪随机数列 :Rn=Xn M (6) 其中其中 , c,M以及初值以及初值X0都是正整数容易看出都是正整数容易看出 满足满足0 Rn 1 若若c 0且且 1，则称这种方法为混合同余法当

7、，则称这种方法为混合同余法当c=0时，时，Xn+1= Xn (mod M )， 0 Xn+1 M ，Rn=XnM ， (7) 称为乘同余法称为乘同余法 13 同余法 当当=1 ，C 0时，时，Xn+1=Xn+C (mod M)，0 Xn+1 M ， Rn=Xn M， (8) 称为加同余法称为加同余法 虽然加同余法产生的序列周期长，电子计算机实现也很方便，虽然加同余法产生的序列周期长，电子计算机实现也很方便， 只要进行加法及移位运算即可完成，但从理论上看，所得到随只要进行加法及移位运算即可完成，但从理论上看，所得到随 机数列的性质一般不如乘同余法和混合同余法机数列的性质一般不如乘同余法和混合同余

8、法 若若 =c=1，则有，则有Xn+1=Xn+1(mod M)这样构成的序列虽然周期这样构成的序列虽然周期 可以达到可以达到M，但不是随机的。因此乘子，但不是随机的。因此乘子 ，增量，增量C的选取是非常的选取是非常 重要的重要的. 二、二、Monte-Carlo方法设计思想方法设计思想 MonteCarlo方法的是：对要解决的数值 计算问 题，构造适当的概率模型，使要得到的解正好 重合于概 率模型中随机变量的概率分布或数字特 征，其后在计算 机上用伪随机数列对随机变量进行 模拟得到一个大子样 的观测数据，进行统计整理以 后，给出问题的一个近似 估计因此，MonteCarlo 方法是双重近似，一

9、是将数 值计算问题用概率模型 作近似，二是在计算机上用伪随 机数作近似抽样值 进行统计整理作出一些估计。 为了应用MonteCarlo方法对上述的3类(6 种)生成伪 随机数的方法进行比较，设计如下的数学 实验： 设g(x)是0，1上的连续函数，且0g(x) 1考 虑定积分的值 如图1所示，在单位正 方形内，曲线 y=g(x )右 面的阴影A的面积就是 积分值s 由此想法构造计算定积分的投点模型 向正方形0z1，0Y1内均匀投点( 是相互独立的均匀随机数 列，第i次试验成功，即( )落入A 中，也就是满足 g(e)，若每 次成功的 概率为P，进行 次试验成功了k次，则由 大数定理知 即n 充分

10、大时，kn依概率收敛 到P由于P=s，因 此常取 skn 三、数学实验结果及分析三、数学实验结果及分析 下面应用上述MonteCarlo方法对第一部分所 述的3类(6种)生成伪随机数方法进行比较，其步 骤是：首先用算法产生随机数，然后用所生成的随机 数进行简单的定积分计算以计算积分 为例 显然由直接积分得 现在用投点方法来计算，以kn作为 ，的近似值，这 里k是n次投点试验中，使不等式 成立的个数 下面将用 分别产生随机 数列，并用投点法来计算上述4个积分 伪代码： #include stdafx.h #include #include #include using namespace std

11、; const long M=2097152;/2 21 const long N=1600000; /实验的次数 void rand1(long /混合同余法 void rand2(long /乘同余法 void rand3(long /加同余法 void rand4(long /平方取中法 void rand5(long /乘积取中法 void rand6(long /移位法 float f(float x,int k);/y=xk void main() int i; int n; long k6=0,0,0,0,0,0,A82,j; float I6; A00=19;A01=37; A

12、10=19;A11=37; A20=19;A21=515; A30=37;A31=129; A40=1234;A41=5829; A50=6513;A51=3245; A60=4158;A61=3023; A70=797152;A71=315023;/初值 for (n=2;n10;n+) for(j=1;jN;j+) rand1(A00,A01);/混合同余法 rand2(A10,A11);/乘同余法 rand3(A20,A21);/加同余法 rand3(A20,A21);/为了增加独立性,取其偶 数项 rand3(A30,A31);/加同余法 rand3(A30,A31);/为了增加独立性

13、,取其偶 数项 rand4(A40);/平方取中法 rand4(A41);/平方取中法 rand5(A50,A51);/乘积取中法 rand5(A60,A61);/乘积取中法 rand6(A70);/移位法 rand6(A71);/移位法 for(i=0;i2;i+) if(1.0*Ai1)/Mf(1.0*Ai0)/M,n) ki+; if(1.0*A20)/Mf(1.0*A30)/M,n) k2+; if(1.0*A41)/10000f(1.0*A40)/10000,n) k3+; if(1.0*A50)/10000f(1.0*A60)/10000,n) k4+; if(1.0*A71)/M

14、f(1.0*A70)/M,n) k5+; for(i=0;i6;i+) Ii=(1.0*ki)/N; coutshowpointfixedleftsetprecision(4); coutn=nendl; cout试验次数N=N,不同随机数产生算法的实验果:endl; cout混合同余法t乘同余法t加同余法endl; coutI_n=setw(12)I0; coutI_n=setw(12)I1; coutI_n=setw(12)I2endl; cout平方取中法t乘积取中法t移位法endl; coutI_n=setw(12)I3; coutI_n=setw(12)I4; coutI_n=setw(12)I5endlendlendl; for (j=0;j6;j+) kj=0; void rand1(long /a2,c2分别为乘子 和增量 x1=(a0*x1+c0)%M; x2=(a1*x2+c1)%M; void rand2(long /a2为乘子 x1=(a0*x1)%M; x2=(a1*x2)%M; void rand3(long t=x2; x2=(x1+x2)%M; x1=t; void rand4(long void rand5(long t=x2; x2 =(x1*x2)/100)%10000; x1=t; void rand6(long float f