随机数生成器一、随机数1.1随机数的概念数学上是这样定义随机数的：在连续型随机变量的分布中，最简单而且最基本的分布是单位均匀分布。

由该分布抽取的简单子样称为随机数序列，其中每一个体称为随机数。

单位均匀分布即［0，1］上的均匀分布。

由随机数序列的定义可知，ξ1，ξ2，…是相互独立且具有相同单位均匀分布的随机数序列。

也就是说，独立性、均匀性是随机数必备的两个特点。

1.2随机数的分类随机数一般分为伪随机数和真随机数。

利用数学算法产生的随机数属于伪随机数。

利用物理方法选取自然随机性产生的随机数可以看作真随机数。

实用中是使用随机数所组成的序列，根据所产生的方式，随机数序列再可以分为两类：1．伪随机数序列伪随机数序列由数学公式计算所产生。

实质上，伪随机数并不随机，序列本身也必然会重复，但由于它可以通过不同的设计产生满足不同要求的序列且可以复现（相同的种子数将产生相同的序列），因而得到广泛的应用。

由伪随机数发生器所产生的伪随机数序列，只要它的周期足够长并能通过一系列检验，就可以在一定的范围内将它当作真随机数序列来使用。

2．真随机数序列真随机数序列是不可预计的，因而也不可能出现周期性重复的真正的随机数序列。

它只能由随机的物理过程所产生，如电路的热噪声、宇宙噪声、放射性衰变等。

按照不同的分类标准，随机数还可分为均匀随机数和非均匀随机数，例如正态随机数。

1.3随机数的衡量标准在实际模拟过程中，我们一般只需要产生区间[0,1]上的均匀分布随机数，因为其他分布的随机数都是由均匀分布的随机数转化来的。

实用中的均匀随机数主要通过以下三个方面来衡量其随机性能的高低。

1．周期性伪随机数序列是由具有周期性的数学公式计算产生，其本身也必然会表现出周期性，即序列中的一段子序列与另一段子序列相同。

它的周期必须足够长，才能为应用提供足够多的可用数据。

只有真随机数序列才能提供真正的、永不重复的随机数序列。

2．相关性随机数发生器所产生的一个随机数序列中的各个随机数应该不相关，所产生的各个随机数序列中的随机数也应该不相关。

真随机数序列自然地满足这种不相关性。

对于伪随机数发生器，应该仔细地设计所用的数学公式，以尽量满足不相关的要求。

3．分布均匀性包括蒙特卡洛计算在内的大多数应用都要求所采用的随机数序列服从均匀分布，即同一范围内的任一个数出现的概率相同。

从均匀分布的随机数序列也很容易导出其它类型分布的随机数序列。

1.4常用的随机数生成方法目前已经出现了多种随机数生产生方法，主要有以下三种 1．人工方法通过拋硬币、扔骰子等方法获得随机序列。

由这类方法产生的随机序列具有高度的随机性，但是这种方法效率极低。

2．利用计算机生成伪随机数这是最常见的随机序列产生方法，它是基于“随即种子”产生的。

由计算机算法来获得的随机序列是有规律可循的，所以其安全性较差。

3．通过检测随机噪声源来获取真随机数产生真随机数需要熵源即随机源，目前熵源一般是通过检测放射性衰变、粒子轨迹、电子电路噪声、大气噪声、机械振动噪声、电子振荡器频率抖动等物理噪声来获取的。

由于这些装置结构复杂，操作繁琐，有些还对人体具有一定的危险性，使得目前这类随机数产生方法既不方便，也不实用。

二、利用计算机生成伪随机数的方法2.1 平方取中法2.1.1迭代算法平方取中法是由冯·诺依曼提出的。

它的实现方法为：首先任取一个非0的2m 位的数，用它中间的m 位数码作为所生成的伪随机序列的第一个元素，然后将该数做平方运算，得到一个新的2m 位的数，取其中间m 位作为伪随机序列的第二个元素，依次进行。

当取十进制时，用公式可表示为：)10](mod 10[22/1m n m n r r ⨯=-+2.1.2程序及讨论 sum=0;x(1)=65215; m=5; n=100; for i=1:nx(i+1)=mod(10^(-m/2)*x(i)^2,10^m); r(i)=x(i+1)*10^(-m); sum=sum+r(i); endplot(r,'.'); grid on ;Avg=sum/n %均值 s=0; for i=1:ns=s+(r(i)-Avg)^2; endS=s/(n-1) %方差 Stdv=S.^0.5 %标准差 figure; hist(r,5);axis([-0.1,1.1,0,28]); colormap([0.8,0.8,0.8]);图1和图2为初值x0=65215时由平方取中法得到的伪随机序列和统计直方图。

)(x E =0.5117，)(x D =0.0758，)(x σ=0.2753。

0102030405060708090100平方取中法产生的伪随机序列00.20.40.60.81统计直方图（平方取中法）图1 平方取中法产生的随机序列（x0=65215） 图2 随机序列统计直方图（100点） 图3和图4为初值x0=500时由平方取中法得到的伪随机序列和统计直方图。

可以看到从86点以后序列全部退化为0。

)(x E = 0.4000，)(x D = 0.1030，)(x σ = 0.3209平方取中法产生的伪随机序列00.20.40.60.81统计直方图（平方取中法）图3 平方取中法产生的随机序列（x0=500） 图4 随机序列统计直方图（100点） 这种方法比较容易实现，但是它的周期受初始值的影响很大，初始值选得不好，会严重影响随机数序列的质量和周期。

2.1.3周期退化问题这种平方取中法并不是生成伪随机序列的好方法。

它的缺点在于这样产生的序列中很容易出现重复元素的短循环，而且，一旦某一个元素是0，则后面所有的元素都将是0（如图3）。

如果生成的序列中，有从最高位开始连续m/2个0的数，则产生的序列会逐渐退化到0。

这是因为在十进制表示的情况下：2/10m n r <，2/210m n n r r ⨯<，则由迭代公式可得：n n r r <+1。

或者生成的序列中，有从最低位起至少连续的m/2+1个0的数，则产生的序列也会逐渐退化到0。

这是因为：如果生成序列中n r 满足上述条件，则2n r 从末位起至少有m+2个0，即是说，i n r +末位的0比1-+i n r 末位的0多，从而逐渐退化为全0。

当生成的序列中，有从最低位起有连续的m/2个0的数，则生成的序列元素，从最低位起，有一半的位为0。

它的最长周期已由m 退化为m/2，这样的数，已不适合再称为伪随机数。

平方取中法有一些变形和推广。

其中之一就是：后一个序列元素不再只依赖于前一个元素，而是依赖于前几个，甚至是不相邻的几个序列元素。

这种变形和推广使得序列的周期长度通常大于m ，但产生的序列的随机性需要经过检验。

2.2 线性同余法LCG (Linear Congruence Generator)2.2.1迭代算法在伪随机数的产生方式中最常见的就是线性同余法，生成公式：0,mod )(1≥+=+n m c aX X n n其中： m ，模数；m>0a ，乘数；0 ≤a <m c ，增量；0 ≤c <m0X ，初始值，种子；0 ≤0X <m如果这些参数和种子(初值)都指定，序列也就确定下来了。

通常取M X r i i /=作为区间(0，1)上均匀分布U(0，1)的随机数。

线性同余法中一个最重要的特例是c=0，这时也称乘同余法。

当模数M 足够大时，用线性同余法产生的随机数在区间（0，1）很密集，而且接近均匀分布，其随机数序列具有较好的统计特性。

虽然序列的参数，如乘子、增量和模数对随机数的质量和周期影响很大，但是它们都有自己的选取准则，可以使产生的随机数序列性能最优。

模数m 取得较大，序列的周期才可能较大。

当c ＝0时，生成序列可能达到的极大周期等于模数m 的欧拉函数φ(m)，若满足：1）初始值r0与m 互素， 2）乘数a 是模m 的本原元， 则可以实现这一周期。

2.2.2程序及讨论x(1)=1; a=14; c=0; m=17; n=100; sum=0; for i=1:nx(i+1)=mod(a*x(i)+c,m); r(i)=x(i)/m; sum=sum+r(i); endplot(r,'.');grid on ;Avg=sum/n %均值 s=0; for i=1:ns=s+(r(i)-Avg)^2; endS=s/(n-1) %方差 Stdv=S.^0.5 %标准差grid on ;图5产生的序列为M X r i i /=，其中17mod 141i i X X =+，i r 被看作是 (0，1)上的随机数。

当0X =1时，它产生周期为16的如下序列i X ：1,14,9,7,13,12,15,6,16,3,8,10,4,5,2,11,1…010203040506070809010000.20.40.60.81统计直方图（线性同余法）图5 线性同余法产生的随机序列 图6 随机序列统计直方图（100点） （a=14,c=0,m=17）)(x E = 0.4982，)(x D = 0.0744，)(x σ = 0.2728令100mod )311(1+=+i i X X ，产生周期为50的序列如图7。

0102030405060708090100线性同余法产生的伪随机序列00.20.40.60.81统计直方图（线性同余法）图7 线性同余法产生的随机序列 图8 随机序列统计直方图（100点） （a=11,c=3,m=100）)(x E = 0.4950，)(x D = 0.0841，)(x σ = 0.2899容易看出，线性同余发生器有长周期相关现象。

在应用中，我们应特别警惕和回避这种现象。

如果几个并行处理器分别使用同一个同余序列的不同段落，分割时就应避开具有强相关的分点。

另外其周期和分布受参数影响显著，例如，图5周期为16，图7周期为50；图5所示序列分布不够均匀（见图6）。

参考：（0,1）均匀分布的均值为0.5，方差为0.0833，标准差为0.2887。

2.3Fibonacci 序列2.3.1迭代算法Fibonacci 方法也是产生随机数的一种常用方法，它只要两个初值和一个模数即可，其递推公式如下所示：M X X X i i i mod )(11-++=从公式可以看出，用此方法产生的随机数序列周期为3M/2，而且没有乘法运算，因此其生成速度非常快，物理实现也十分简单。

2.3.2程序及讨论 x(1)=1;x(2)=1; m=100; n=100; sum=0; for i=2:nx(i+1)=mod(x(i)+x(i-1),m); r(i)=x(i)/m; sum=sum+r(i); endplot(r,'.'); grid on ;Avg=sum/n %均值 s=0; for i=1:ns=s+(r(i)-Avg)^2; endS=s/(n-1) %方差 Stdv=S.^0.5 %标准差 figure; hist(r,5);axis([-0.1,1.1,0,25]); colormap([0.8,0.8,0.8]);图9和图10为初值x0=1，x1=1，m=100时由Fibonacci 序列生成的100点伪随机序列和统计直方图。