随机数生成方法、随机数生成法比较以及检验生成的随机序列的随机性的方法

摘要本文着重讨论了随机数生成方法、随机数生成法比较以及检验生成的随机序列的随机性的方法。在随机序列生成方面，本文讨论了平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、取小数法等，并比较了各方法的优劣性。在统计检验方面，介绍了统计检验的方法，并用其检验几种随机数生成器生成的随机数的随机性。最后介绍了两种新的随机数生成法，并统计检验了生成随机序列的随机性。关键词：随机数，随机数生成法，统计检验ABSTRACTThisarticlefocusesonmethodsofrandomnumbergenerator,randomnumbergenerationmethodcomparisonandtesttherandomnessofthegeneratedrandomsequencemethod.Inrandomsequencegeneration,thearticlediscussesthesquaremethod,Fibonaccimethod,laggedFibonaccimethod,theshiftmethod,linearcongruentialmethod,linearcongruencemethod,takingminoritylaw,andComparisonofadvantagesanddisadvantagesofeachmethod.Instatisticaltest,theintroductionofthestatisticaltestmethod,andusedtotestsomerandomnumbergeneratorrandomrandomnumbersgenerated.Finally,twonewrandomnumbergenerationmethod,andstatisticaltestsofrandomnesstogeneratearandomsequence.KeyWords:randomnumber，randomnumbergenerator，statisticaltest目录TOC\o"1-5"\h\z第1章引言 1\o"CurrentDocument"课题背景 1\o"CurrentDocument"1.2课题的价值及意义 1\o"CurrentDocument"课题的难点、重点、核心问题及方向 1第2章随机数 3\o"CurrentDocument"基本概念 3\o"CurrentDocument"产生随机数的一般方法 3\o"CurrentDocument"随机数生成的数学方法 4\o"CurrentDocument"产生随机数的方法种类 5\o"CurrentDocument"随机数的应用 6\o"CurrentDocument"第3章常见随机数生成法与比较 7\o"CurrentDocument"3.1平方取中法 73.1.1迭代算法 73.1.2平方取中法的优缺点 7\o"CurrentDocument"斐波那契(Fibonacci)法 8\o"CurrentDocument"滞后斐波那契(Fibonacci)法 9\o"CurrentDocument"移位法 9\o"CurrentDocument"线性同余法 10\o"CurrentDocument"模数的选取 10\o"CurrentDocument"乘数的选取 11线性同余法的缺陷 12广义线性同余法 12\o"CurrentDocument"非线性同余法 13\o"CurrentDocument"逆同余法 13二次同余法 14三次同余法 14\o"CurrentDocument"BBS法 14\o"CurrentDocument"取小数法 14\o"CurrentDocument"3.8常见随机数生成法的比较 15\o"CurrentDocument"第4章随机数生成法的统计和检验 16\o"CurrentDocument"检验类型 16\o"CurrentDocument"4.2统计检验的一般方法 16\o"CurrentDocument"4.2.1参数检验 174.2.2均匀性检验 18\o"CurrentDocument"4.2.3重要分布 18\o"CurrentDocument"4.2.4重要定理 19\o"CurrentDocument"4.2.5卡方检验 20\o"CurrentDocument"4.2.6柯氏检验 20\o"CurrentDocument"4.2.7序列检验 21\o"CurrentDocument"独立性检验 22\o"CurrentDocument"对线性同余法和取小数法进行随机性检验 22\o"CurrentDocument"第5章新的随机数生成法 24\o"CurrentDocument"5.1开方取小数法 24\o"CurrentDocument"5.2一种混合型随机数发生器 28超素数长周期法 285.2.2组合发生器的研究 305.2.3随机数算法统计检验结果 30\o"CurrentDocument"结束语 32\o"CurrentDocument"参考文献 33\o"CurrentDocument"致谢 34\o"CurrentDocument"外文资料原文 35\o"CurrentDocument"翻译文稿 37第1章引言第1章引言课题背景随机数（随机序列）在不同的领域有许多不同类型的应用。如雷达中的测距信号，遥控遥测中的测控信号，数字通信中的群同步和加扰解扰信号，无线通信码分多址系统中的扩频信号等都要用到随机序列。在用计算机的教学与学习中，也经常需要用到随机数，比如，数据结构中关于一个数据的存储地址，在各种程序设计语言学习中遇到的随机量的生成，图像处理中遇到的随机色彩的选择等，枚不胜举，随机数在计算机的应用中就显得格外重要。尤其在仿真等领域，更对随机数的产生提出了较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。现实中，用投色子计数的方法产生真正的随机数，但电脑若也这样做将会占用大量内存；虽然用噪声发生器或放射性物质也可产生真正的随机数，但操作不可重复。而用数学方法产生随机数则最适合计算机，这就是“伪随机数”。我们需要的随机数序列应具有非退化性，周期长，相关系数小等优点。迄今为止，研究人员提出了许多不同的随机数生成方法，如平方取中法，同余法，斐波那契序列变形法，混沌序列法，利用系统时间和热噪声等等。随着新的随机数性能测试方法的提出，已经证明其中的某些生成方法有其固有的缺陷。同时对测试方法的研究也是一个不断发展的过程。课题的价值及意义由于现在对随机数的公认定义中，只给出了随机数的性质描述，而没有给出其生成方法，同时现有的所有检测方法也只是给出了一些必要而非充分的条件。因此，随机数的生成及其性能检测方法，都有待于进一步的研究。具体的应用环境不同，对随机数发生器的性能要求就不一样，而不同的随机数发生器产生的随机数的性质必然不一样。为了能对一个随机数发生器的性能做一个比较全面和客观的评价，需要对不同的测试方法进行研究，讨论其测试目的和测试依据。本课题主要是讨论随机数生成法，随机数生成法比较以及随机数的检测统计，从上面分析看出，本课题是很有意义和开拓性的工作。课题的难点、重点、核心问题及方向本课题的核心问题是随机数生成法、随机数生成法比较以及随机数的统计检验。本课题的主要工作内容如下：（1）介绍几种常见的随机数生成法，并比较了各种随机数生成法的优劣；（2）介绍统计检验的理论，并对几种随机数生成法进行了统计检验（3）介绍新的随机数生成法，并对随机数进行统计检验。第2章随机数在用计算机的教学与学习中，经常需要用到随机数，比如，数据结构中关于一个数据的存储地址，在各种程序设计语言学习中遇到的随机量的生成，图像处理中遇到的随机色彩的选择等，不胜枚举，随机数在计算机的应用中就显得格外重要。尤其在仿真等领域对随机数的产生提出了更较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。现实中，用投色子计数的方法产生真正的随机数，但电脑若也这样做，将会占用大量内存；虽然用噪声发生器或放射性物质也可产生真正的随机数，但操作不可重复。而用数学方法产生随机数则最适合计算机，这就是“伪随机数”。我们需要的随机数序列应具有非退化性，周期长，相关系数小等优点。基本概念在密码学中，对于一个随机序列的定义如下：（1）看起来是随机的。（2）这个序列是不可预测的。（3）这个序列是不能重复产生的。随机变量耳的抽样序列耳,n，…耳，…，称为随机数列。如果随机变量耳是均匀TOC\o"1-5"\h\z1 2 n分布的，则n的抽样序列耳,n，…耳，…，称为均匀随机数列；如果随机变量耳 是1 2 n正态分布的随机变量则称其抽样序列为正态随机数列。随机序列具有以下性质：（1） 等分布性：随机序列的分布特性是等概分布，或称为一致分布。即是说序列中每个元素出现的概率都是相等的。（2） 独立性：随机序列的各个元素之间是相互独立的。（3） 不可预测性：该性质可由等分布性和相互独立性推出。（4）白噪声谱特性：由独立性可知，随机序列的自相关函数为5函数。产生随机数的一般方法随机数产生方法的研究己经有很长的历史，至今仍有统计学者继续研究随机数产生的方法和理论。产生随机数的一般方法:（1） 手工方法:这是随机数产生的最早方法，即采用抽签、掷筛子、抽牌、摇号或从搅乱的罐子中取带数字的球等方法。（2） 随机数表方法:Monte-Carlo方法的出现，需要大量的随机数，显然用手工的方法不能满足模拟计算的需要。1927年Tipett造出了具有4万个随机数字的表;1939年Kendell和Babington-Smith用高速转盘建立了有+万个数字的随机数表;兰德(Rand)公司利用电子装置产生了含有一百万个数字的随机数表。在电子计算机产生之前人们就是利用这些随机数表进行统计模拟计算。物理方法:随着计算机和模拟方法的广泛应用，用计算机产生随机数成为新的课题。在计算机上安装一台物理随机数发生器，把具有随机性质的物理过程变换为随机数，使用物理随机数发生器在计算机上可以得到真正的随机数，随机性和均匀性都是很好的，而且是取之不尽用之不竭的。但是此方法也有一些缺点，其中最重要的是我们不能产生同原来完全相同的随机数，对计算结果不能进行复算检查;加上物理随机数发生器的稳定性经常需要进行检查和维修，因而大大降低了这种方法的使用价值。数学方法:它是利用数学递推公式来产生随机数的;它是目前使用最广泛、发展很快的一类方法;它的特点是占用内存少、速度快又便于计算。本文主要是介绍用数学方法来产生随机数的算法，即各种各样的随机数发生器。随机数生成的数学方法用数学方法产生随机数，就是利用计算机能直接进行算术运算或逻辑运算的特点，选取一个适宜的数学递推公式；+m二f(?；，；+m丿，利用计算程序，按递推公式对数字进行加工处理，把°丄…,bm-1或其部分数字的自然顺序打乱，产生具有均匀总体、简单子样统计性质的随机数，这里一般m取较小的正整数，：为机器的字长。用数学方法产生的随机数的速度快，占用内存少，对模拟的问题可以进行复算检查，一般还有较好的统计性质．但是，由于计算机只能表示有限位不同的数，严格说，在计算机上不能产生真正连续分布的随机数，只能产生离散分布的随机数来代替连续分布的随机数．另外，计算机上用数学方法产生随机数，是根据确定的算法推算出来的，因此严格说来，用数学方法在计算机上产生的“随机数”不能说是真正的随机数，故一般称之为“伪随机数”。随机数生成方式有真随机和伪随机两种。真随机数生成法满足以上关于随机序列定义的所有三点要求，伪随机数生成法只满足前两点要求。不过对这些伪随机数，只要通过统计检验符合一些统计要求，如均匀性、随机性等，就可以作为真正的随机数来使用。所以本文在后面章节将会介绍随机数、随机数生成法、随机数生成法比较以及随机数的统计检验。在计算机上用数学方法产生随机数的一般要求如下：产生的随机数列要有均匀性、抽样的随机性、试验的独立性和前后的一致性；产生的随机数列要有足够长的周期，以满足模拟实际问题的要求；产生随机数的速度要快，占用的内存少。数学方法生成随机数的过程如下：(1)找到一个数学模型或算法。设置其中参数的值。通过某种运算产生种子即第一个随机数。然后在产生的种子的前提下，生成第二个随机数。通过同样的步骤，就产生了一个随机数序列。从上可以看出，计算机中伪随机数序列的产生有两大要素，一是产生随机数序列的初始值，称之为随机种子；二是产生随机数的计算方法，即随机函数。计算机的伪随机数序列是由随机种子根据一定的计算方法计算递推出来的序列。伪随机数生成器将作为“种子”的数当作初始整数传给函数。这粒种子会使这个球(生成伪随机数)一直滚下去。伪随机数生成器的结果仅仅是不可预测。由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定，最终，该种子决定了一切。如果知道用于计算任何一个值的那个整数，那么就可以算出这个生成器返回的下一个值。结果，伪随机数生成器是一个生成完全可预料序列的确定性程序。只要计算方法一定，随机种子一定，那么程序每次产生的随机数序列就是固定的。通常而言，计算方法是不容易改变的，而随机种子是可以随时改变的，程序每次运行时可赋予不同的随机种子从而得到不同的序列。产生随机数的方法种类由于产生随机数的计算方法(随机函数)不同，现在大体有以下几种常见方法：平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、混沌序列法、取小数法等。一个好的随机数发生器应当具备以下几点条件:(1)产生的随机数序列要具有均匀总体随机样本的统计性质，如分布的均匀性，抽样的随机性，数列间的独立性等等。(经验检验)产生的随机数序列要具有较好的理论支持(或具有好的格结构)，如分布的谱检验(Spectraltest)和高维分布检验(k-distributiontest)。(理论检验)产生的随机数序列要有足够长的周期，以满足模拟计算的需要。产生的随机数序列的速度快，占用计算机的内存少，具有完全可重复性。随着计算机运算速度的不断提高，存储容量和字长的不断扩大，(3)和((4)两点一般都能满足;至于条件(2)属于理论方面的问题，由于涉及到很多数论等基础数学方面的内容，本文不做过多的研究。因此，关键是如何构造满足(1)的随机数发生器，即做大量的统计检验工作。下面章节将详细介绍各方法，并分析比较各方法的优缺点，最后对各方法做统计检验工作。随机数的应用随机序列有许多不同类型的应用。诸如用于仿真各种自然现象，用于检验计算机程序设计中的随机化算法，甚至有时候被人们用来做决策。同时随着计算机技术、通信技术的充分发展，信息在传递、处理、存储过程中的安全问题已引起了人们的广泛关注．信息安全领域内的核心问题之一就是如何制作高质量的随机数发生器和产生随机数的方法。现在，随机数已广泛应用于在密码算法方面、安全协议方面、数字水印方面等信息安全领域在很多情况下，系统决策需要进行多次仿真比较才能确定，重现性非常必要因此，在计算机上生成伪随机数及对伪随机数进行检验的问题就受到人们的重视模拟计算表明，通过改进伪随机数的品质，可使计算机仿真结果的有效性得到明显提高，在有些情况下甚至可使仿真结果的数值相对误差缩小为原来的1/10或更小。因此，进行伪随机数发生器的研究，具有重要的理论意义和应用价值。第3章常见随机数生成法与比较由于产生随机数的计算方法(随机函数)不同，现在大体有以下几种常见方法：平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、混沌序列法、取小数法等。平方取中法产生伪随机数列最早的方法是平方取中法，它是由冯•诺依曼提出的。迭代算法此法开始取一个2s位的整数，称为种子，将其平方，得4s位整数(不足4s位的高位补0)，然后取此4s位的中间2s位作为下一个种子数，重复上述过程，即可得到一系列随机数。平方取中法的递推公式为:TOC\o"1-5"\h\zx=[x2/10s](mod102s) (3—1)n+1 n产生伪随机数列：r=x/102s (3—2)nn平方取中法的优缺点平方取中法的优点为在计算机上易于实现，内存占用少，但仍存在对小数目偏倚的现象，均匀性不好，对初始数据的依赖很大，数列的长度和周期难以确定，很容易出现重复元素的短循环，而且，一旦某个元素是0，则后面所有的元素都将是0。如果生成的序列中，有从最高位开始连续s个0的数，则产生的序列会逐渐退化为0°这是因为在十进制表示的情况下：厂＜10s,厂2＜厂X10s,则由(3—1)可得r＜r°n nn n+1n或者生成的序列中，有从最低位起至少连续的「s]+1个0的数，则产生的序列也会逐渐退化到0°这是因为：如果生成序列中r满足上述条件，则r2从末位起nn至少有2s+2个0,即是说r末位的0比r末位的0多，从而逐渐退化为全0°n+i n+i-1

当生成的序列中，有从最低位起有连续的s个0的数，则生成的序列元素，从最低位起，有一半的位为0。它的最长周期已由2s退化为s，这样的数，已不适合再称为伪随机数。平方取中法有一些变形和推广。其中之一就是：后一个序列元素不再只依赖于前一个元素，而是依赖于前几个，甚至是不相邻的几个序列元素。这种变形和推广使得序列的周期长度通常大于2s，但产生的序列的随机性需要经过检验。另一种就是对平方取中法进行改进的方法是，乘积取中法，如果要产生具有1O进制2s位的伪随机数列，任取两个初始随机数x,x，用递推公式：01x=[xx/IOs](mod102s) (3-3)n+2 n+1n产生伪随机数列：r=x/102s (3—4)nn乘积取中法与平方取中法比较，从产生的伪随机数列长度及均匀性方面都有改善但是数列长度还是不够，而且对初始值的依赖性很大。3.2斐波那契(Fibonacci)法斐波那契法是基于Fibonacci序列，其递推公式为:=(x+x)modm(n=1,2,…)3-5)(n=1,2,…)3-5)xr=fnm显然，斐波那契法有两个初始种子x和x。方法的最大特点就是计算速度很01快，且达到满周期。但是序列中数重复出现，独立性较差。此发生器没有乘法运算，产生速度快．但是它存在着令人不能容忍的不居中现象，即由前两个数得到的第三个数要不是同时大于就是同时小于前二者而永不居中。此序列的另一个缺点是显著的序列相关，即取小值的数后面出现也取小值的趋势。所有这些都说明它不是一个好的随机数序列。

3.3滞后斐波那契(Fibonacci)法滞后的斐波那契法是斐波那契法的推广，目前存在很多种形式。下面仅仅给出一种比较有名的方法，其递推公式为:=(x+=(x+x)modmn-pn—q(n=0,1,…)3-6)nm其中p>q>0，初始种子为(x,x，…,x)。-1-2 -p3.4移位法计算机善于进行移位等逻辑运算，应用计算机的这个特点有一类产生伪随机数列的方法，该方法称为移位法。本方法是关于平方取中法的一种改进形式，它是移位运算与指令相加运算相结合的迭代过程。它的思想是：首先选取一个初始值x，使之左右移位，分别为x和x，然后00102指令相加得x，再对x进行上述过程，如此重复下去，便可得随机数序列。对于113-7)字长为32位的计算机，这一算法的递推公式为：3-7)x=27x+2-7x(mod232)n+1 n n产生伪随机数列：r=x/232 (3-8)nn移位法运算速度快，但是对初始值的依赖性也很大，一般地初始值不能取得太小选得不好会使伪随机数列长度较短。同时m(m>1)维均匀随机向量相关性大，即独立性较差。最后随机数序列周期T与计算机的字长有关。3.5线性同余法同余法(LinearCongruentialGenerator,LCGforshort是Lehmer于1951年提出来的，此方法是利用数论中的同余运算原理来产生随机数，有线性同余法非线性同余法等，其中线性同余法法又分为加同余法、乘同余法以及混合同余法同余法是现在发展迅速且使用普遍的方法之一。首先介绍下线同余法。线性同余法的递推式为：x=ax+c(modm) (n=0,1,2,…) (3-9)n+1 n式中参数a,c和m分别称为乘、增量和模，x为种子。如果这些参数和种子(初值)0都指定序列也就确定下来了。通常取r=讣(n=0,1,2,…)作为区间(O,1)上均匀nm分布U(0,1)的随机数。从上可以看出当c=0，为乘同余法；当a=1,ch0时，为加同余法，否则称为混合同余法。按惯例，当强调使用某方法产生随机数时，常使用某方法(随机数)发生器的称呼。线性同余法有如下特点:0<x<m+1。i适当选取m,a,c可使x循环，无论x取何值，其循环顺序相同，其循环i0周期称为发生器周期，记为T。若T=m，则称之为满周期。适当选取m,a,c，可保证x在[[0,1〕区间上一个周期内每个整数正好出i现一次，从而保证了均匀性。为提高r的均匀性，要求加大m。i下面讨论下线性同余中参数的选取。模数的选取从线性同余的生成公式中可以看到，生成序列x的最长周期不可能超过m。n为得到较长的周期，需要选择较大m值。考虑m的另一个方面是实现时的生成速度。在二进制计算机上，进行模运算，最好选择模数m=2e的形式。这样模运算，只需要进行位与操作就可以实现了。但是这种简单的选择，在某些应用中，却不是令人满意的。这里，假设选取m=2e，则d=24是m的一个因子。这里d的指数选取为4是因为我们假设只考察生成序列元素x的最低四个比特位的规律。y三x(modd) (3-10)nny三x(modd)=(ax+c)(modd)三(ay+c)(modd) (3—11)n+1n+1 n n可以看到，由序列x的各元素低三比特位组成的序列是一个周期更短的同余n序列。它的最长周期为16。类似的，x低三位的最长周期为8，x低五位的最长nn周期为32，等等。x的最低位不是常数，就是O,1交替。这在强调低位随机性的n应用中，是不令人满意的。为避免这种缺陷，可以选择模数m二2e土1，或者是选取m为小于2e的最大素数。对于模数m=2e+1的情况，(xmodm)有快速实现方法(见附录)：n注意上述算法中，第7步其实是一个递归调用。整个算法中只有加减，位与，移位，比较和跳转操作。对于m=2e-1的情况也是类似的。乘数的选取模数m取得较大，序列的周期才可能较大。下面的定理1指出了得到极大周期所应满足的条件：由m,a,c和x所定义的线性同余序列有周期长度m，当且仅当：0c与m互素；对于整除m的每个素数p，b=a-1是p的倍数；如果m三0(mod4)，则b三0(mod4)。该定理的证明过程见附录。在有些情况下，可能会利用c=0(此时为乘同余法)来获得较快的生成速度。根据定理1,这时生成序列不可能达到极大周期聊。但仍然可以通过选择乘数a来使得序列周期尽可能地长。在生成公式(3-9)中，取c=0，m二pe，则x三anx(modpe) (3-12)n0显然，周期是使得x=aTx(modpe)的最小正整数T。如果x与pe的最大公000因子是pf，则由数论定理，得到：aT三1(modpe-f) (3-13)由数论欧拉定理可知：a牡p-f)三l(modpe-f) (3-14)所以，T必是p(pe-f)的一个因子。欲使得T为最大，应当取T等于p(pe-f)・且若x与pe互素，则此时T等于P(pe-f)=pe-i(p一1)。并且当a是模m的一个本0原元时，aT三1(modm)中T取得极大值p(m)。综上所述，得出下面的结论：当c=0时，生成序列可能达到的极大周期等于模数m的欧拉函数p(m)，若满足：初始值x与m互素；0乘数a是模m的一个本原元，则可以实现这一周期。3.5.3线性同余法的缺陷TOC\o"1-5"\h\z线性同余序列众所周知的缺陷是其高维稀疏网格结构：当把相继的t个随机数(r,r，…,r)，看作是m维空中上的一个点时，这些点只散布在m维空间的的nn+1 n+m少数几个超平面上，并形成稀疏的网格结构。为说明线性同余法的问题，首先给出一个极简单的线性同余发生器：x=14x(mod17) (n=0,1,2，…)，其中r=x/m(n=0,1,2，…)被看作是\o"CurrentDocument"n+1 n n n(0,1)上的随机数。当x=1时，它产生周期为16的如下序列1，14,9，7，13，0l2，15，6，l6，3，8，l0，4，5，2，ll，1•容易看出，x=17一x，即其前\o"CurrentDocument"n 8+n半段与后半段的相关系数为一1，这便是同余发生器的长周期相关现象。MatteisPagnuttir已从理论上证明了所有线性和非线性同余序列都存在长周期相关现象。在应用中，我们应特别警惕和回避这种现象。如果几个并行处理器分别使用同一个同余序列的不同段落，分割时就应避开具有强相关的分点。3.5.4广义线性同余法广义线性同余发生器(Generalizedlinearcongruentialgenerator,GLCGforshort)是线性同余发生器的推广，其递推公式为：x=f(x•,x，…，x )(modm) (n=0,1，…) (3-15)n+k nn+1 n+k-1

其中f是x•,x，…,x的确定性函数。nn+1 其中f是x•,x，…,x的确定性函数。nn+1 n+k-13.6非线性同余法80年代末开始，许多学者已经开始讨论非线性同余发生器(Nonlinearcongruentialgenerator,NLCGforshort)，其递推公式的一般形式为：x=f(x)(modm)n+1 nx

r=—n、 nm(n=0,1,…)3-16)公式(3-17)中的xgZ二｛0,1…,m-1｝，而f是Z上的一个整数函数。若n m mf(x)=ax+c，则公式(3-17)就是线性同余发生器。在非线性同余中f是Z上n n m的一个排列多项式，这时有｛f(0),f(1),…,f(m-1)｝二Z。m下面介绍几种比较典型的非线性同余发生器:逆同余法、二次同余法、三次同余法和BBS法。3.6.1逆同余法逆同余发生器(Inversivecongruentialgenerator,ICGforshort)，是非线性同余类中的最有前途的一种随机数发生器。其递推公式为:=(ax+b)mod(n=0,1,2...)3-17)nm其中对于cgZ(m为素数)，定义cC=1modm且cgZ(若c=0，定义c=0)，这时mm称C为c关于模m的乘法逆。逆同余法的主要优点在于能克服高维网格结构.例如模为M=231-1的逆同余发生器可以通过直至230维的网格检验．而线性同余发生器要保证10维以内近似最优的网格结构都有困难(请参考Fishman—Moore，1986)．然而逆同余法的周期不比线性同余法的长，Matteis-Pagnutti(1990)也从理论上证明了所有逆同余序列也都象线性同余序列那样存在长周期相关现象。另外，从应用上看，逆同余法的速度明显慢于线性同余。二次同余法二次同余的生成表达式：x=(dx2+ax+c)(modm) (3-18)n+1 n n上式产生的序列有周期长度m，当目仅当：c与m互素，对所有整除m的奇素数p，d和a-1都是p的倍数；如果m是4的倍数，则d是偶数，而且d三a-1(mod4):如果m是2的倍数，则d三a一1(mod2)；如果m是9的倍数，则d丰3c(mod9).二次同余是一般线性同余的推广，由以上的结论可以看出，要获得极大周期m所需的条件限制并不比线性同余法更严格。三次同余法三次同余的生成表达式:x=(ax3+bx2+cx+d)(modm) (3-19)n+1 nnn其中a,b,c,d均为正整数，且a丰0，m为正整数模，x°为初始种子。数a、c、m的取值满足一定条件时,才可得到较好结果。BBS法BBS发生器是由Blum和Shub共同提出的一种随机数发生器。其递推公式x=x2modm(i=0,1,2...) (3-20)i+1 i3.7取小数法这种方法不能直接用公式表达,其原理是将前一次随机数平方后的数,取其小数点后第一个非零数字后面的尾数作为下一个所求的随机数。3.8常见随机数生成法的比较前面介绍各种随机数生成法时，已经大概介绍了下各种方法的优缺点。现在再简要比较下各种随机数生成法的优缺点。平方取中法的优点是计算简单,计算机上易于实现，内存占用少，缺点是种子的选择很重要,对初始数据的依赖很大，否则很难保证有足够长的周期,而且容易出现退化现象(以后的随机数为同一常数或为0)。斐波那契法的优点是计算简单,计算速度很快，周期较长且达到满周期，可证明为1.5m。缺点序列中数重复出现，独立性较差。此发生器没有乘法运算，产生速度快．但是它存在着令人不能容忍的不居中现象，即由前两个数得到的第三个数要不是同时大于就是同时小于前二者而永不居中。此序列的另一个缺点是显著的序列相关，即取小值的数后面出现也取小值的趋势。所有这些都说明它不是一个好的随机数序列。移位法运算速度快，但是对初始值的依赖性也很大，一般地初始值不能取得太小，选得不好会使伪随机数列长度较短。同时m(m1)维均匀随机向量相关性大,即独立性较差，存在稀疏网格，最后随机数序列周期T与计算机的字长有关。线性同余法是一种较好的方法,目前很多仿真语言中使用的就是这种方法。其缺点是高维稀疏网格结构，有长周期相关现象，相对而言其计算要复杂些,而且只有公式中的常数m,a,c的取值满足一定条件时，才可得到较好结果。非线性及逆同余的缺陷是长周期相关，周期依赖机器字长，产生效率低。取小数法的优缺点类似于平方取中法，而且要求种子一般应取纯小数，并且数字位要尽量多。第4章随机数生成法的统计和检验随机数的好坏如何，即它们的性质究竟与真正的［0,1］区间上的均匀分布的随机变量的简单随机样本的性质有无显著差异，是一个很重要的问题。如果有显著差异，则以这种随机数发生器产生的随机数为基础的随机变量所抽得的样本，实际上将不能反映该随机变量的性质，从而所得随机模拟的最后的结果将是不可靠的。因此对随机数进行检验，将是很重要的工作。在进行统计检验之前，下面首先简单介绍一些统计检验的基础知识。检验类型一般情况下有两种不同的检验方法:(1)经验检验:经验检验是一种统计检验，它是以发生器产生的均匀随机数序列｛xi｝为基础的，根据［0，1］区间上均匀总体简单随机样本｛ui｝的性质，如特征向量、均匀性、随机性等，研究我们产生的随机数序列｛叮的相应性质，进行比较、鉴别、视其差异是否显著，决定取舍。理论检验:理论检验从统计意义上讲并不是一种检验。它是一种综合的方法来评估发生器的数值参数，而根本不必产生任何随机数序列｛xi｝，即它是一种理论上的研究。本章主要介绍一些经验检验，对于理论检验由于涉及过多的专门学科的知识数学上相当困难的，本章不再给予讨论。统计检验的一般方法统计检验的一般方法有以下几种：参数检验:均匀随机数的参数检验是检验由某个发生器产生的随机数序列｛xi｝的均值、方差和各阶矩等与均匀分布的理论值是否有显著的差异。均匀性检验:随机数的均匀性检验又称频率检验，它是来检验由某个发生器产随机数序列｛xi｝时，是否均匀地分布在区间［0，1］上。也就是检验经验频率与理论频率的差异是否显著。独立性检验:独立性检验主要是检验随机数序列x「分…Xn之间的统计相关性是否显著。即判别每个数的出现是否与其前后各数独立无关。

（4）无连贯性检验：将依次出现的N伪随机数，按其大小分为两类或者k类，则各类数的出现是否有连贯现象。对于参数检验，由于随机数服从标准均匀分布U（°，l）,则其均值和方差的理论值分别为：H=0.5q2=1/12 （4-1）当样本容量充分大时，可用正态分布进行检验。利用兀2拟合优度检验（取10个区间）可以检验所产生的随机样本的总体分布是否为均匀分布。利用游程检验法检验随机样本的独立性，其中游程是由连续0或者1组成的序列，并且其前后元素与游程的元素不同．游程数目为序列长度的一半产生的随机序列较好。4.2.1参数检验若随机变量R〜U（0,1若随机变量R〜U（0,1），则E（R）= Var（R）=丄,E（R2）=1，若R,R，…,R是2 12 3 1 2 n即R,R，…,R相互独立同U（0,1）分布。记fR-1]li2丿i均匀总体的简单随机样本，R=-Lrni

i=112R2=1工ni=1R2

i1ns2=Lni=1则有：E(则有：E(R)Var（R）=丘；E(r2)=1E(r2)=1，3E(s2)=丄,12VarVar(R2)=(s2)445n118on设r,r，…,r是某个发生器产生的随机数。首先对特征量作统计检验。在｛r｝是均匀1 2 n i总体的简单随机样本的假设下，统计量：

_1r2—_1r2—3、445nVarr2?11)S2———1)S2———12丿^Var\s2)12、^Var\s2)渐进服从N(0,1)。给定显著水平a后，查标准正态数值表得：九:P舊卜X)_a,C〜N(0,1)),否定域Wju|i｝(i_1,2,3)。由随机数列｛r｝计i i i i i算u,耸u的值，若|u|<X，则认为产生的随机数序列的特征量与均匀总体的特征量没有显著差异；否则由于｛r｝得特征量与均匀总体特征量有显著差异，故不能认为｛r｝是均匀总体的简单样本。i均匀性检验均匀性检验中常用的方法有:卡方检验、柯氏检验和序列检验。4.2.3重要分布(1)二项分布：(4-2)如果随机变量x的所有可能取值为k_0丄2,…,n，且x取值k的概率为(4-2)p_Ckpk(1—p)n—k，k_0,1,2,…，nk n则称X服从参数为n,p的二项分布，记为x〜B(n,p)。当k取值仅为0,1时，又称x服从0-1分布或两点分布。(2)正态分布：如果随机变量X的概率密度函数为：f(xf(x)4-3)则称随机变量X服从参数为CQ2)的正态分布，记为X〜NCQ2)。如果卩=0,b=1，则称X服从正态分布，记为X〜NC，Q2)。其分布函数记为：①(z①(z)=1z Je_u2/2du—g4-4)%2分布设x,xx是来自于标准正态总体N(0,1)的独立样本，则由它们构造的统计12n量X=£x2服从自由度为n的%2分布。自由度为n的%2分布的概率密度函数为:ii=1xn/2—1xn/2—1e—x/24-5)f(x,n)=<2n/2r(n/2)4-5)其中伽玛函数r(z)=gxz-le-xdx，而r(a)=r(a,0)。对一般的伽玛函数，有r(a,x)=gta—ie-tdt。特别地，对于a为整数n的情况，有:xr(n,x)=(n—1)! -6)k!k=0重要定理(1)Pearson定理利用总体的样本值xx x来检验总体的分布函数是否为F(x)。1,2n先设定原假设H:X的分布函数为F(x)，F(x)为某已知分布函数。取k-1个

点，满足：tYt...Yt将实数轴分为k个区间：(—g,t],(t,t (t,+g)。设12 k-1 / 1 12 k—1样本值x,xx中落入第i个区间(t,t]内的个数为v，其相对频数为12n i—1i tv/n,(1<i<k)。i如果原假设H成立，则X落入第i个区间内的概率为：0p=F(t)—F(t),1<i<k (4-7)i i i—1

贝努利定理指出：当n,重复独立实验中事件发生的频数收敛于该事件在每次试验中发生的概率。所以当n充分大时候，二-p应该比较小。从而得出ni工f二-p「上兀(一叫1也应该较小。匚11n '丿Pi匚1叫Pearson指出：假设H成立，则当n充分近似服从自由度为k-rT的咒2分布,0其中r是F(x)中被估计的参数个数。在实际应用中，一般要求np>5，以保证i误差不会太大。(2)中心极限定理DeMoivre-Laplace定理：设随机变量耳服从参数为n，p的二项分布，则对于任意x，有limPnts耳一limPnts耳一npx〉=dt4-8)由此可见，二项分布的极限分布是正态分布。4.2.5卡方检验设r,rr是待检验的一组随机数，假设H:r,rr为均匀总体的简单样12n 0 12n本。将【0,1］区间分为m个小区间，以C-1/m,i/m)(i=1,2,...,m)表示第i个小区间，设{r}i(j=1,2,...,n)落入第i个小区间的数目为n(i=1,2,...,m)。i根据均匀性假设，r落入每个小区间的概率为1/m，第i个小区间的理论频数nju=—(i=1,2,...,n)统计量：imy(n-卩匕my(n)2

V=厶一i i—=一厶In—一1 u nIim丿i=1 i i=1渐进服从x2(m—1)。给定显著性水平a，查x2分布表得临界值后，即可对经验频率与理论频率的差异作显著性检验(本章卡方检验中取区间数m=500)。4.2.6柯氏检验柯氏检验是连续分布的拟合性检验。它检验样本的经验分布函数与总体的分布

函数间的差异u是否显著。设随机数为r,r，…,r,从小到大排序后得下,下，…,下。记经验分布函数为F(x)；12n12nn将F(x)与均匀分布的分布函数F(x)=x(0<x<1)比较，其最大偏差即柯氏检验统n计量为：V=max6+,D-)=max\i-「r _in_—-f(—-f(r),nf(r)-匕in其中，D+=maxnD-=maxn1D-=maxn1<i<n利用V渐进地服从柯氏分布这一事实进行显著检验。24.2.7序列检验序列检验实际上是用于多维分布的均匀性检验，它也间接地检验序列的独立性。已知随机数序列｛r｝C=1,2,...,2n)，将容量为2n的随机数一次配对为：v=(r,r),v=(r,r),...,v=(r,r)1 122 34n 2n-12n如果｛r｝是均匀随机数列，那么它们应该构成平面上正方形内的二维均匀随机向量的样本。将单位正方形分成k2个灯面积的小正方形，、表示｛v｝(i=1,2,...,n)落入第(i,j)个小正方形的频数，理论频数卩=n/k2。则检'验统计量：ij33nIji=1j=1n)2k2丿在｛r｝为均匀分布的独立抽样序列成立时渐进地服从x2(2-1)i(r,r,...,r12n将以上二维的序列检验可以推广到三维，四维直至一般的d维。即对｛.｝(r,r,...,r12nv=2(r ,r,...,r ),d+1d+2 2d(v=kr,r ,...,r(k-1)d+1(k-1)d+2 kdv1它们应该是在单位d维超立方体［o,1B中均匀分布的独立随机样本。把［0,1］区间分成m个相等的小区间，相应地把单位d维超立方体分成md个小超立方体，用n 表示｛v｝落入第(j,jj)个超立方体的个数。统计量：j1j2...jd k 12kV=md艺JEfn -丄f3n Ijj2-jdmd,A=1jd=1渐进服从x2(md-1)(nTs)。这种d维均匀分布的检验(序列检验)间接地检验了｛r｝的独立性i独立性检验独立性检验中常用的方法有:相关系数检验工、相关系数检验工I、列联表检验和游程检验。对线性同余法和取小数法进行随机性检验我们取样本量n=1000，分别对取小数法和线性同余法进行检验。下面我们就上面所述线性同余法中参数a，c和m的取值分别采用在36位和32位计算机上常用的算法：a=515，c=1，m=231 (4—9)4—10)a=314115926，c=453806245，m=2314—10)c=0称为乘同余法，为了提高乘同余法的可用性，人们进行了大量的研究，发现可通过恰当的选择m及a，可以接近满洲期，较突出的是素数取模同余法，下面给出两个经过检验的性能较好的素数取模同余法，它们是X二52X(mod235-31) (4—11)i i-1X=75X(mod231-1) (4—12)i i-1随机数算法检验表如下：

算法种子样本均值样本方差均值检验方差检验拟合检验独立性检验4.2.110.48120.0848-2.060.6315.240.02100.50300.08270.33-0.268.040.811000.49030.0848-1.060.638.64一0.814.2.210.48670.0859-1.461.1119.181.51100.49710.08450.580.519.38-0.151000.50130.08460.740.5512.18-2.364.2.310.49510.0862-0.541.215.28-1.34100.48400.0832-1.76-0.0714.280.351000.50670.08460.740.5512.18-2.364.2.410.49800.0788-0.22-1.917.56-1.36100.49960.0803-0.04-1.316.64-0.731000.49710.0873-0.311.7019.58-0.09取小数法0．10.49520.0818-0.53-0.6510.68-1.170.20.50970.08201.06-0.5511.32-0.530.30.53470.08543.800.8824.72-0.30取a=0.05,当V|<1.96,通过均值检验；当V|<1.96则通过方差检验；当|V|<16.92.则通过均值检验;当|V|<1.96,则通过独立性检验•上表给出了5个随机数发生器其中前4个均为线性同余法，最后一个是作者提出的取小数法。每个线性同余算法的参数，都是经过专家精心选出的。由表1可以看到。对于不同的种子（每个发生器各取3个种子），它们通过检验的机会基本一致（各有一个种子通不过检验）。我们看到，线性同余法不仅与种子有关，而且与参数m,a,c的选取有关。为了保证其统计性质，一般将m取得很大•这样，在计算过程中，为防止整数溢出还要进行一些算法处理。而取小数法只与种子的选取以及计算机字长有关。可以认为，取小数法不失为一种简单实用的随机数发生器。

第5章新的随机数生成法5.1开方取小数法在常见的伪随机数产生法中，只要种子取得得当，取小数法仍不失为一种好方法。根据取小数法原理，我们将前一次随机数开方后的数，取其小数点后第一此方法生成的随机数的好坏，即是否很好的满足上文提到的重要条件，要进行验证。对于周期问题，这种方法同取小数法，只要不退化，周期可说是无穷的对于均匀性和独立性要求，下面用统计学知识对它加以检验。以下是用开方取小数法生成的200个数，种子为2，我们可以其为样本进行检验，生成的200个数如下。0.4142140.4359420.6025920.762680.7331560.5624540.499690.06890960.6250650.9061030.5189420.2037620.5140010.1693850.1156460.4006810.3299410.7440470.6258160.9108550.5438740.374780.1219290.4918360.0131010.14460.8026360.9589940.792820.904060.50082080.1288730.5898870.6804080.486820.9868030.9337960.6633120.1443970.7999580.9440360.7161490.4625610.8011810.9508730.7512730.6676020.1706890.1314480.6255730.9093170.5358110.3199140.6560930.0999550.16156

0.0194470.3945370.2812160.3029820.5043790.101963 0.1931650.3950580.2853620.3419260.8474450.2056750.5351420.315340.615510.8454480.1948220.4138680.4332570.5822270.630379 0.9396390.694980.327650.7240720.5092450.136140.6897140.30490.5217770.2234110.7266380.5243080.2409130.9082880.5304150.2829570.3193710.6512940.0702770.6509850.0683650.6146720.8401020.1657060.0706960.6588790.1171330.4224720.4997840.0695440.6371170.9819590.9093840.5361610.3223040.6771850.2291230.7866810.8695020.3247090.6983240.3565770.9714060.8559930.251990.0198640.40940.3984370.3121870.5873680.6639910.1485640.8544040.2434010.9335640.6621120.1370280.7017260.3769080.1392860.7320980.5562730.4583680.7702870.7765970.8124740.0137360.1719970.1472530.8373560.1507180.8822380.3927550.2670140.1673360.0906660.0110850.0528320.2985270.4637580.8099780.9998780.999390.9969470.9847240.9233260.6089880.8037670.9653060.8250.0829490.8800980.3813530.1753820.187860.3342770.7816670.8411920.1716540.1431120.7830110.848790.2129810.6149890.8421220.1767210.2038150.5145870.1734750.1650360.0624650.4992940.0660740.5704840.5530410.4366690.6080960.7980520.9333740.661130.130990.6192550.869273工u i200工u i200二0.500567S2二丄工（u-uA=0.084274n一1我们知道服从u（0,1）分布的均值我们知道服从u（0,1）分布的均值1

u=—21，万^差b2— -12取统计量X，YX1=疇=疝_1）u一一2丿而且有:e（u）-2D（u）-12n当n充分大的时候，则应有X，Y都近似服从N(0,1)分布。11取a=0.05，查正态分布表Z—=1.962由于X|=0.02777Y1.96由于|Y|=0.178479Y1.96所以在显著性水平a=0.05条件下，可以接受总体均值u=2,方差。2=丄的假设。12F面再用Z2拟合优度检验法对这些数作分布均匀性检验。我们将样本的取值范围分布在10个等宽区问，即分成0~0・1,0・1~0・2,0・2~0.3,0・3~0.4,0・4~0.5,0.5~0.6,0.6~0.7,0.7~0.8,0.8~0.9,0.9~1,10个区间统计实际落在每个区间内的样本个数ni如下：i12345678910ni16301520152026171920如对均匀分布，则这些数落在第i个区间内的概率：pi=/按X2拟合法，取统计量VV=丄工ni2/pi一nnV=工ni2一n=6.620取a=0・O5,查自由度k-1=10- 1=9的X2分布表X爲,9=16.92》|V|=6.6故应接受显著水平为a=°・°5的均匀性假设。由上面可知这些随机数服从u(0,1)分布。对于独立性，我们可用游程检验法来检验。将这些随机数分别与均值u=0・5相减，取其符号得到一个正负号序列如下：统计其中的正号个数n二104,负号个数n二96,游程数r二9412假设这些数是独立分布的，取统计量r则应有E(r)=2nn1十—+n+n212=100.34D(r)二2nn(2nn-n-n)1__2 1_2 1 2—(n+n^(n+n-1)1212二49.59r近似于正态分布。由于Z=理)=94竺=-0.9r阿取a=0.05，查正态分布表Z=a21.96aZ1=0.9r故应接受这一假设。由上面的检验可知，种子取2时，用这种方法生成的随机数比较好。我们可称这种方法为开方取小数法，也可当作取小数法的另外一种形式。这种方法优于取小数法的地方在于种了的选取条件要宽松很多，我通过编制一个计算机程序对该算法进行了模拟，除了完全平方自然数(如1,4,9,16)以外，大于零的数大多能当作种了使用。显然，这给用户提供了方便，这种方法不失为一种好的随机数生成法。归纳起来，此算法有如下优点（1）算法简单，除初始值外没有其他参数。（2）序列与初值的取值关系不大，几乎可以取得所有非负有理数。（3）数列就具有周期长，不易退化，统计性质好等优点。缺点:如何取适当的种子?5.2一种混合型随机数发生器20世纪五、六十年代，随着计算机的发展，出现了用线性同余法（LCG）和移位寄存器法产生随机数的方法，并一直得到广泛的应用。但是随着理论与实践的深入，这些方法的缺陷及间题的严重性进一步暴露，比如线性同余法的稀疏网格，长周期相关，周期依赖机器字长的缺陷，移位寄存器的稀疏网格，随机性依赖于初始值，存在微妙相关的缺陷。近十余年又出现许多产生随机数的新方法。例如，非线性同余法，特别是其中的逆同余法，进位加/借位减/进位乘发生器以及乘子和增量也在递推中变化的复合素数发生器和各种组合发生器。然而，单个发生器仍存在一些缺陷。与已有的方法不同，用超素数生成伪随机数的方法和优选乘子的超素数伪随机数法，对原算法作了改进，它的主要思想为:在原有的随机数发生器的基础上，利用超素数的重要性质，结合线性同余发生器，提出新的组合算法，产生随机数组合发生器。这种新的随机数生成算法旨在提高随机数的独立性。5.2.1超素数长周期法不难看出，三种方法（一般超素数法、优选乘子超素数法以及混合同余法的周期都是2的整数倍（用2n来表示）。这种周期有一个严重缺陷:如果在一个周期内同时取出相互间隔的两类随机数a类和b类，在一个周期有n个属于a,n个属于b。很明显a类和b类的数是不一样的，而在下一个周期同样是重复上一个周期，也就是说，无论生成随机数有多少，a类和b类的随机数是不一样的。比如说在1*1的方框内作图，如果生成一个随机数来表示x坐标，再生成一个随机数来表示y坐标，那么x和y的取值范围是不一样的。比如说，周期为10，其中，0，012,014,016,018为一类，011,013,015,017,019为一类，这两类数的范围不一样，用来模拟过程所得到的结果也是有差异的。这类方法在用于并行计算等场合时会由于随机数本身产生统计上的偏差。为避免产生统计偏差，我们提出改进方法，即结合增量的方法，使增量不是一个常数C,而是让增量每次增加I,相应生成随机序列的迭代模式为：Z=九Z+C(modM)，C=C+1i+1 i i+1 i+1 i计算表明，经过该变换得到的随机序列周期为M(M—1)。由于理论分析困难,周期为M(M—1)的结论尚难于给出严格的证明。但是，本文检验了小于45016的所有超素数，周期都为M(M—1)，且如果分成A和B两类，［0,M—1］范围的每一个数在每一类中出现的次数都是(M-1)/2，只是在每一类中的排序不一样。当M为45061时周期己经大于2幻09，足以满足常规模拟的需要，故从实用角度而言上述结论是成立的。下面以7为例说明。九=10，Z=1，C=1C—2，Z=10x1+2(mod7)=5选 0 0得1 1继续下去，得C2=3,Z2=4以此类推所得到的结果如表1所示。表1不同样本容量k=5时的相关系数N1020100100010000100000M=9735370.561.702.070.1531.43x10-23.58x10-3M=1048710.962.602.340.1284.51x10-3-3.74x10-3由表1可见，在一个周期内，［O,M-1］的整数都出现了M—1次，同时出现的顺序更加无规律(因不再包含M-1个数的片断反复重复，由M个不同的包含M-1个数的片段组成)，把它分成两类后的结果如表2和表3所示。表2模数为1048571时的优选乘子1033108110971193121712231259130113031381153115431567162116631697170917771783178918612017表3以模数为7的长周期算法余数序列542445216112653556320223064660431334105001542445216112653556由表3可见，在A，B两类中出现O,M-1的所有整数次数都为(M—1)/2，在这里就是三次。这样可避免上面出现的问题，即A类和B类出现的数不一样。5.2.2组合发生器的研究在各种各样的新方法中，组合随机数发生器是最值得关注的。组合发生器是指几个不同随机数发生器组合所得的一类发生器。例如几个线性同余发生器（LCG）的线性组合或几个移位寄存器序列（FRS）的线性组合。原则上说，被组合的发生器可以不限于同一个类型。但是，不同组合的理论分析是十分困难的。用LCG法产生随机数，有一些缺陷，主要是该方法产生的均匀随机数作为M维均匀随机向量时相关性大。其次利用超素数法产生随机数序列均匀性和独立性方面不是很理想。为克服LCG法和超素数法的上述缺陷，得到均匀性和独立性更好的随机数，利用组合发生器所依据的原则，即打乱数列的次序使之排列不规则。先用超素数长周期法所产生的随机数序列作为随机数表，再用乘同余发生器所产生的随机数对其进行重新排列得到的数列作为新的随机数列，其算法为:用超素数长周期法产生L个随机数，这L个随机数被顺序存放在数组中；（2）用线性同余发生器产生一个随机整数j,要求1-j-L;（3令，然后再用超素数长周期法产生一个随机数y,令tj二y。5.2.3随机数算法统计检验结果统计检验结果见下列统计表格，表中列出了超素数长周期法和乘同余发生器的统计性质，以便比较，其中组合发生器是由超素数长周期法的随机数发生器和一个线性同余发生器利用组合发生器算法产生的随机数序列。由以下统计数据表4至表6可知，超素数长周期法形成的组合发生器在独立性与周期这两个特性上都得到了明显的改善，具有很好的统计性质，可以用作随机数发生器。表4不同样本容量下各种方法的均值检验的统计值样本数1X1021X1031X1041X1051X1061X107超素数长0.5040910.4972470.499280.5001880.5002440.500162周期法线性同余0.5221350.5056620.5006010.49980.5000160.500154法组合发生0.5153240.5151920.4966120.5006710.5002120.500124器表5不同样本容量下各种方法的均匀性检验的统计值样本数1X1021X1031X1041X1051X1061X107超素数长1411.5214.48414.87430.88035.939周期法

线性同余28.413.9210.06415.88419.145723.125法组合发生14.422.6412.84413.97028.33234.3345器表6几种随机数发生器的统计性质比较（N=10000）超素数长周期法线性同余法组合发生器初值111周期2030448660536870912Ta210分组区间数202020相距K555一阶矩0.499280.5006010.496612二阶矩0.3318860.3337870.329965二阶中心距0.083017850.08318380.0833523均匀性检验14.48410.06412.844独立性检验-0.0001490210.000449672-0.000148083我们提出了一种新的随机数发生器算法，即由超素数长周期法和线性同余法利用组合发生器算法生成新的随机数序列。经过大量数据的统计检验，新的随机数发生器算法得出的随机数序列通过了参数检验，均匀性检验，独立性检验，故可以作为随机数发生器。组合发生器的独立性较组合前的超素数长周期法和线性同余法提高很多。相关性非常弱，因此在独立性上比现有的随机数算法都要优越组合发生器的均匀性较超素数长周期法提高很多。经过组合算法打乱随机数序列后，稀疏网格的现象明显改善。结束语随着计算机的飞速发展，产生随机数的发生器类型也越来越多，但是到目前为止人们越来越重视组合随机数发生器的优越性。本文就讨论了常见的随机数发生器，并且对发生器的优劣性进行了比较，同时结合已有的随机数发生器的特点提出了一种新的随机数发生器，也给出了一种特殊（即仅仅给出两种发生器的组合）的组合随机数发生器，并且给出了统计检验。参考文献[1]杨自强，魏公毅，综述:产生随机数的若干新方法.2000.[2]徐钟济,蒙特卡罗方法.上海:上海科技大学出版社.1985.林国顺，陈佳，一种随机教发生器新算法的研究[J]大连海事大学学报.2005.F.N.DavidandD.E.Barton,CombinatorialChance.NewYork:HafnerPublishingCo.,1962,p230.Tezuka,S.Uniformrandommunbers:theoryandpractice.Nowell,Mass;KluwerAcademicPublishers,1955.张咏，随机数发生器和随机数性能检验方法研究，电子科技大学硕士学位论文.2006.张广强，均匀随机数发生器的研究和统计检验，大连理工大学硕士学位论文.2005.杨自强,魏公毅，常见随机数发生器的缺陷及组合随机数发生器的理论与实践.2001致谢值此论文完成之际，首先感谢我的导师段勇。在段老师的耐心指导下我才能够完成这篇论文．段老师让我领略到微分方程数值解这门学科的魅力，激发了我对这一领域的兴趣，增加了我对这领域的向往。在此，谨向我的指导老师致以最崇高的敬意和忠心的感谢。其次我还要感谢电子科技大学给我提供了一个团结，友好，平和的环境，让我能够在这样和谐而且积极的环境学习。我还要感谢应数一班的所有同学，谢谢你们四年来的支持和鼓励。最后我要谢谢我的父母这二十多年来对我生活学习上的关心和支持。外文资料原文ParallelRandomNumberGeneration:Long-RangeCorrelationsAmongMultipleProcessorsKarlEntacher,AndreasUhl,andStefanWegenkittlAbstract.WeuseanempiricalstudybasedonsimpleMonteCarlointegrationstoexhibitthewellknownlong-rangecorrelationsbetweenlinearcongruentialrandomnumbers.Incontrasttoformerstu