《2022年随机数生成方法、随机数生成法比较以及检验生成的随机序列的随机性的方法 .pdf》由会员分享，可在线阅读，更多相关《2022年随机数生成方法、随机数生成法比较以及检验生成的随机序列的随机性的方法 .pdf（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、摘 要I 摘要本文着重讨论了随机数生成方法、随机数生成法比较以及检验生成的随机序列的随机性的方法。在随机序列生成方面，本文讨论了平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、取小数法等，并比较了各方法的优劣性。在统计检验方面，介绍了统计检验的方法，并用其检验几种随机数生成器生成的随机数的随机性。最后介绍了两种新的随机数生成法，并统计检验了生成随机序列的随机性。关键词：随机数，随机数生成法，统计检验名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 41 页 -ABSTRACT II ABSTRACT This article focuses on meth
2、ods of random number generator,random number generation method comparison and test the randomness of the generated random sequence method.In random sequence generation,the article discusses the square method,Fibonacci method,lagged Fibonacci method,the shift method,linear congruential method,linear
3、congruence method,taking minority law,and Comparison of advantages and disadvantages of each method.In statistical test,the introduction of the statistical test method,and used to test some random number generator random random numbers generated.Finally,two new random number generation method,and st
4、atistical tests of randomness to generate a random sequence.Key Words:random number，random number generator，statistical test 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 41 页 -目录III 目录第 1 章引言.11.1 课题背景 .11.2 课题的价值及意义 .11.3 课题的难点、重点、核心问题及方向.1第 2 章随机数.32.1 基本概念 .32.2 产生随机数的一般方法 .32.3 随机数生成的数学方法 .42.4 产生随机数的方法种类 .52
5、.5 随机数的应用 .6第 3 章常见随机数生成法与比较.73.1 平方取中法 .73.1.1 迭代算法 .73.1.2 平方取中法的优缺点 .73.2 斐波那契(Fibonacci)法.83.3 滞后斐波那契(Fibonacci)法.93.4 移位法 .93.5 线性同余法 .103.5.1 模数的选取 .103.5.2 乘数的选取 .113.5.3 线性同余法的缺陷 .123.5.4 广义线性同余法 .123.6 非线性同余法 .133.6.1 逆同余法 .133.6.2 二次同余法 .143.6.3 三次同余法 .143.6.4 BBS 法.143.7 取小数法 .14名师资料总结-精品
6、资料欢迎下载-名师精心整理-第 3 页，共 41 页 -目录IV 3.8 常见随机数生成法的比较.15第 4 章随机数生成法的统计和检验.164.1 检验类型 .164.2 统计检验的一般方法 .164.2.1 参数检验 .174.2.2 均匀性检验 .184.2.3 重要分布 .184.2.4 重要定理 .194.2.5 卡方检验 .204.2.6 柯氏检验 .204.2.7 序列检验 .214.3 独立性检验 .224.4 对线性同余法和取小数法进行随机性检验.22第 5 章新的随机数生成法.245.1 开方取小数法 .245.2 一种混合型随机数发生器.285.2.1 超素数长周期法 .
7、285.2.2 组合发生器的研究 .305.2.3 随机数算法统计检验结果 .30结束语 .32参考文献 .33致谢.34外文资料原文 .35翻译文稿 .37名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 41 页 -第 1 章 引言1 第1章 引言1.1 课题背景随机数(随机序列)在不同的领域有许多不同类型的应用。如雷达中的测距信号，遥控遥测中的测控信号，数字通信中的群同步和加扰解扰信号，无线通信码分多址系统中的扩频信号等都要用到随机序列。在用计算机的教学与学习中，也经常需要用到随机数，比如，数据结构中关于一个数据的存储地址，在各种程序设计语言学习中遇到的随机量的生成，图像处理
8、中遇到的随机色彩的选择等，枚不胜举，随机数在计算机的应用中就显得格外重要。尤其在仿真等领域，更对随机数的产生提出了较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。现实中，用投色子计数的方法产生真正的随机数，但电脑若也这样做，将会占用大量内存；虽然用噪声发生器或放射性物质也可产生真正的随机数，但操作不可重复。而用数学方法产生随机数则最适合计算机，这就是“伪随机数”。我们需要的随机数序列应具有非退化性，周期长，相关系数小等优点。迄今为止，研究人员提出了许多不同的随机数生成方法，如平方取中法，同余法，斐波那契序列变形法，混沌序列法，利用系统时间和热噪声等等。随着新的随机数性能测试方法
9、的提出，已经证明其中的某些生成方法有其固有的缺陷。同时对测试方法的研究也是一个不断发展的过程。1.2 课题的价值及意义由于现在对随机数的公认定义中，只给出了随机数的性质描述，而没有给出其生成方法，同时现有的所有检测方法也只是给出了一些必要而非充分的条件。因此，随机数的生成及其性能检测方法，都有待于进一步的研究。具体的应用环境不同，对随机数发生器的性能要求就不一样，而不同的随机数发生器产生的随机数的性质必然不一样。为了能对一个随机数发生器的性能做一个比较全面和客观的评价，需要对不同的测试方法进行研究，讨论其测试目的和测试依据。本课题主要是讨论随机数生成法，随机数生成法比较以及随机数的检测统计，从
10、上面分析看出，本课题是很有意义和开拓性的工作。1.3 课题的难点、重点、核心问题及方向本课题的核心问题是随机数生成法、随机数生成法比较以及随机数的统计检验。本课题的主要工作内容如下：（1）介绍几种常见的随机数生成法，并比较了各种随机数生成法的优劣；（2）名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 41 页 -电子科技大学学士学位论文2 介绍统计检验的理论，并对几种随机数生成法进行了统计检验；（3）介绍新的随机数生成法，并对随机数进行统计检验。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 41 页 -第 2 章 随机数3 第2章 随机数在用计算机的教学与学习中，
11、经常需要用到随机数，比如，数据结构中关于一个数据的存储地址，在各种程序设计语言学习中遇到的随机量的生成，图像处理中遇到的随机色彩的选择等，不胜枚举，随机数在计算机的应用中就显得格外重要。尤其在仿真等领域对随机数的产生提出了更较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。现实中，用投色子计数的方法产生真正的随机数，但电脑若也这样做，将会占用大量内存；虽然用噪声发生器或放射性物质也可产生真正的随机数，但操作不可重复。而用数学方法产生随机数则最适合计算机，这就是“伪随机数”。我们需要的随机数序列应具有非退化性，周期长，相关系数小等优点。2.1 基本概念在密码学中，对于一个随机序列的
12、定义如下：(1)看起来是随机的。(2)这个序列是不可预测的。(3)这个序列是不能重复产生的。随机变量的抽样序列12,n，称为随机数列。如果随机变量是均匀分布的，则的抽样序列12,n，称为均匀随机数列；如果随机变量是正态分布的随机变量则称其抽样序列为正态随机数列。随机序列具有以下性质：（1)等分布性：随机序列的分布特性是等概分布，或称为一致分布。即是说序列中每个元素出现的概率都是相等的。（2)独立性：随机序列的各个元素之间是相互独立的。（3)不可预测性：该性质可由等分布性和相互独立性推出。（4)白噪声谱特性：由独立性可知，随机序列的自相关函数为函数。2.2 产生随机数的一般方法随机数产生方法的研
13、究己经有很长的历史，至今仍有统计学者继续研究随机数产生的方法和理论。产生随机数的一般方法:(1)手工方法:这是随机数产生的最早方法，即采用抽签、掷筛子、抽牌、摇号或从搅乱的罐子中取带数字的球等方法。(2)随机数表方法:Monte-Carlo 方法的出现，需要大量的随机数，显然用手工的方法不能满足模拟计算的需要。1927年 Tipett造出了具有 4万个随机数字的表;1939名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 41 页 -电子科技大学学士学位论文4 年 Kendell 和 Babington-Smith 用高速转盘建立了有+万个数字的随机数表;兰德(Rand)公司利用电
14、子装置产生了含有一百万个数字的随机数表。在电子计算机产生之前人们就是利用这些随机数表进行统计模拟计算。(3)物理方法:随着计算机和模拟方法的广泛应用，用计算机产生随机数成为新的课题。在计算机上安装一台物理随机数发生器，把具有随机性质的物理过程变换为随机数，使用物理随机数发生器在计算机上可以得到真正的随机数，随机性和均匀性都是很好的，而且是取之不尽用之不竭的。但是此方法也有一些缺点，其中最重要的是我们不能产生同原来完全相同的随机数，对计算结果不能进行复算检查;加上物理随机数发生器的稳定性经常需要进行检查和维修，因而大大降低了这种方法的使用价值。(4)数学方法:它是利用数学递推公式来产生随机数的;
15、它是目前使用最广泛、发展很快的一类方法;它的特点是占用内存少、速度快又便于计算。本文主要是介绍用数学方法来产生随机数的算法，即各种各样的随机数发生器。2.3 随机数生成的数学方法用数学方法产生随机数，就是利用计算机能直接进行算术运算或逻辑运算的特点，选取一个适宜的数学递推公式1(,)nmnnmrfrr，利用计算程序，按递推公式对数字进行加工处理，把10,1,mb或其部分数字的自然顺序打乱，产生具有均匀总体、简单子样统计性质的随机数，这里一般m取较小的正整数，b为机器的字长。用数学方法产生的随机数的速度快，占用内存少，对模拟的问题可以进行复算检查，一般还有较好的统计性质但是，由于计算机只能表示有
16、限位不同的数，严格说，在计算机上不能产生真正连续分布的随机数，只能产生离散分布的随机数来代替连续分布的随机数另外，计算机上用数学方法产生随机数，是根据确定的算法推算出来的，因此严格说来，用数学方法在计算机上产生的“随机数”不能说是真正的随机数，故一般称之为“伪随机数”。随机数生成方式有真随机和伪随机两种。真随机数生成法满足以上关于随机序列定义的所有三点要求，伪随机数生成法只满足前两点要求。不过对这些伪随机数，只要通过统计检验符合一些统计要求，如均匀性、随机性等，就可以作为真正的随机数来使用。所以本文在后面章节将会介绍随机数、随机数生成法、随机数生成法比较以及随机数的统计检验。名师资料总结-精品
17、资料欢迎下载-名师精心整理-第 8 页，共 41 页 -第 2 章 随机数5 在计算机上用数学方法产生随机数的一般要求如下：1)产生的随机数列要有均匀性、抽样的随机性、试验的独立性和前后的一致性；2)产生的随机数列要有足够长的周期，以满足模拟实际问题的要求；3)产生随机数的速度要快，占用的内存少。数学方法生成随机数的过程如下：(1)找到一个数学模型或算法。(2)设置其中参数的值。(3)通过某种运算产生种子即第一个随机数。(4)然后在产生的种子的前提下，生成第二个随机数。通过同样的步骤，就产生了一个随机数序列。从上可以看出，计算机中伪随机数序列的产生有两大要素，一是产生随机数序列的初始值，称之为
18、随机种子；二是产生随机数的计算方法，即随机函数。计算机的伪随机数序列是由随机种子根据一定的计算方法计算递推出来的序列。伪随机数生成器将作为“种子”的数当作初始整数传给函数。这粒种子会使这个球(生成伪随机数)一直滚下去。伪随机数生成器的结果仅仅是不可预测。由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定，最终，该种子决定了一切。如果知道用于计算任何一个值的那个整数，那么就可以算出这个生成器返回的下一个值。结果，伪随机数生成器是一个生成完全可预料序列的确定性程序。只要计算方法一定，随机种子一定，那么程序每次产生的随机数序列就是固定的。通常而言，计算方法是不容易改变的，而随机种子是可以随时
19、改变的，程序每次运行时可赋予不同的随机种子从而得到不同的序列。2.4 产生随机数的方法种类由于产生随机数的计算方法（随机函数）不同，现在大体有以下几种常见方法：平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、混沌序列法、取小数法等。一个好的随机数发生器应当具备以下几点条件:(1)产生的随机数序列要具有均匀总体随机样本的统计性质，如分布的均匀性，抽样的随机性，数列间的独立性等等。(经验检验)(2)产生的随机数序列要具有较好的理论支持(或具有好的格结构)，如分布的谱检验(Spectral test)和高维分布检验(k-distribution test)。(理论检验)(3
20、)产生的随机数序列要有足够长的周期，以满足模拟计算的需要。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 41 页 -电子科技大学学士学位论文6(4)产生的随机数序列的速度快，占用计算机的内存少，具有完全可重复性。随着计算机运算速度的不断提高，存储容量和字长的不断扩大，(3)和(4)两点一般都能满足;至于条件(2)属于理论方面的问题，由于涉及到很多数论等基础数学方面的内容，本文不做过多的研究。因此，关键是如何构造满足(1)的随机数发生器，即做大量的统计检验工作。下面章节将详细介绍各方法，并分析比较各方法的优缺点，最后对各方法做统计检验工作。2.5 随机数的应用随机序列有许多不同类
21、型的应用。诸如用于仿真各种自然现象，用于检验计算机程序设计中的随机化算法，甚至有时候被人们用来做决策。同时随着计算机技术、通信技术的充分发展，信息在传递、处理、存储过程中的安全问题已引起了人们的广泛关注信息安全领域内的核心问题之一就是如何制作高质量的随机数发生器和产生随机数的方法。现在，随机数已广泛应用于在密码算法方面、安全协议方面、数字水印方面等信息安全领域在很多情况下，系统决策需要进行多次仿真比较才能确定，重现性非常必要。因此，在计算机上生成伪随机数及对伪随机数进行检验的问题就受到人们的重视。模拟计算表明，通过改进伪随机数的品质，可使计算机仿真结果的有效性得到明显提高，在有些情况下甚至可使
22、仿真结果的数值相对误差缩小为原来的1/10 或更小。因此，进行伪随机数发生器的研究，具有重要的理论意义和应用价值。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 41 页 -第 3 章 常见随机数生成法与比较7 第3章 常见随机数生成法与比较由于产生随机数的计算方法（随机函数）不同，现在大体有以下几种常见方法：平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、混沌序列法、取小数法等。3.1 平方取中法产生伪随机数列最早的方法是平方取中法，它是由冯 诺依曼提出的。3.1.1 迭代算法此法开始取一个2s位的整数，称为种子，将其平方，得4 s位整数(不足4s位
23、的高位补 0)，然后取此4s位的中间2 s位作为下一个种子数，重复上述过程，即可得到一系列随机数。平方取中法的递推公式为:221/1 0(m od 1 0)ssnnxx（3-1）产生伪随机数列：2/10snnrx（3-2）3.1.2 平方取中法的优缺点平方取中法的优点为在计算机上易于实现，内存占用少，但仍存在对小数目偏倚的现象，均匀性不好，对初始数据的依赖很大，数列的长度和周期难以确定，很容易出现重复元素的短循环，而且，一旦某个元素是0，则后面所有的元素都将是 0。如果生成的序列中，有从最高位开始连续s个 0 的数，则产生的序列会逐渐退化为 0。这是因为在十进制表示的情况下：210,10nss
24、nnrrr，则由（3-1）可得1nnrr。或者生成的序列中，有从最低位起至少连续的1s个 0 的数，则产生的序列也会逐渐退化到0。这是因为：如果生成序列中nr满足上述条件，则2nr从末位起至少有22s个 0，即是说nir末位的 0 比1nir末位的 0 多，从而逐渐退化为全0。名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 41 页 -电子科技大学学士学位论文8 当生成的序列中，有从最低位起有连续的s个 0 的数，则生成的序列元素，从最低位起，有一半的位为0。它的最长周期已由2s退化为s，这样的数，已不适合再称为伪随机数。平方取中法有一些变形和推广。其中之一就是：后一个序列元素
25、不再只依赖于前一个元素，而是依赖于前几个，甚至是不相邻的几个序列元素。这种变形和推广使得序列的周期长度通常大于2s，但产生的序列的随机性需要经过检验。另一种就是对平方取中法进行改进的方法是，乘积取中法，如果要产生具有1O进制2 s位的伪随机数列，任取两个初始随机数01,xx，用递推公式：221/10(m od 10)ssnnnxxx（3-3）产生伪随机数列：2/10snnrx（3-4）乘积取中法与平方取中法比较，从产生的伪随机数列长度及均匀性方面都有改善，但是数列长度还是不够，而且对初始值的依赖性很大。3.2 斐波那契(Fibonacci)法斐波那契法是基于Fibonacci 序列，其递推公式
26、为:21()mod(1,2,)nnnnnxxxmnxrm（3-5）显然，斐波那契法有两个初始种子0 x和1x。方法的最大特点就是计算速度很快，且达到满周期。但是序列中数重复出现，独立性较差。此发生器没有乘法运算，产生速度快但是它存在着令人不能容忍的不居中现象，即由前两个数得到的第三个数要不是同时大于就是同时小于前二者而永不居中。此序列的另一个缺点是显著的序列相关，即取小值的数后面出现也取小值的趋势。所有这些都说明它不是一个好的随机数序列。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 41 页 -第 3 章 常见随机数生成法与比较9 3.3 滞后斐波那契(Fibonacci)法
27、滞后的斐波那契法是斐波那契法的推广，目前存在很多种形式。下面仅仅给出一种比较有名的方法，其递推公式为:()m od(0,1,)nnpnqnnxxxmnxrm（3-6）其中0pq，初始种子为12(,)pxxx。3.4 移位法计算机善于进行移位等逻辑运算，应用计算机的这个特点有一类产生伪随机数列的方法，该方法称为移位法。本方法是关于平方取中法的一种改进形式，它是移位运算与指令相加运算相结合的迭代过程。它的思想是：首先选取一个初始值0 x，使之左右移位，分别为01x和02x，然后指令相加得1x，再对1x进行上述过程，如此重复下去，便可得随机数序列。对于字长为 32 位的计算机，这一算法的递推公式为：
28、7732122(m o d 2)nnnxxx（3-7）产生伪随机数列：32/2nnrx（3-8）移位法运算速度快，但是对初始值的依赖性也很大，一般地初始值不能取得太小，选得不好会使伪随机数列长度较短。同时(1)m m维均匀随机向量相关性大，即独立性较差。最后随机数序列周期T与计算机的字长有关。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 41 页 -电子科技大学学士学位论文10 3.5 线性同余法同余法(Linear Congruential Generator,LCG for short)是 Lehmer于 1951年提出来的，此方法是利用数论中的同余运算原理来产生随机数，
29、有线性同余法、非线性同余法等，其中线性同余法法又分为加同余法、乘同余法以及混合同余法。同余法是现在发展迅速且使用普遍的方法之一。首先介绍下线同余法。线性同余法的递推式为：1(m od)(0,1,2,)nnxaxcmn（3-9）式中参数,a c和m分别称为乘、增量和模，0 x为种子。如果这些参数和种子(初值)都指定序列也就确定下来了。通常取(0,1,2,)nnxrnm作为区间(O，1)上均匀分布(0,1)U的随机数。从上可以看出当0c，为乘同余法；当1,0ac时，为加同余法，否则称为混合同余法。按惯例，当强调使用某方法产生随机数时，常使用某方法(随机数)发生器的称呼。线性同余法有如下特点:(1)
30、01ixm。(2)适当选取,m a c可使ix循环，无论0 x取何值，其循环顺序相同，其循环周期称为发生器周期，记为T。若Tm，则称之为满周期。(3)适当选取,m a c，可保证ix在0,1区间上一个周期内每个整数正好出现一次，从而保证了均匀性。(4)为提高ir的均匀性，要求加大m。下面讨论下线性同余中参数的选取。3.5.1 模数的选取从线性同余的生成公式中可以看到，生成序列nx的最长周期不可能超过m。为得到较长的周期，需要选择较大m值。考虑m的另一个方面是实现时的生成速度。在二进制计算机上，进行模运算，最好选择模数2em的形式。这样模运算，只需要进行位与操作就可以实现了。但是这种简单的选择，
31、在某些应用中，却不是令人满意的。这里，假设选取2em，则42d是m的一个因子。这里d的指数选取为 4 是因为我们假设只考察生成序列元素nx的最低四个比特位的规律。名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 41 页 -第 3 章 常见随机数生成法与比较11(m od)nnyxd（3-10）11(m od)()(m od)()(m od)nnnnyxdaxcdaycd（3-11）可以看到，由序列nx的各元素低三比特位组成的序列是一个周期更短的同余序列。它的最长周期为16。类似的，nx低三位的最长周期为8，nx低五位的最长周期为 32，等等。nx的最低位不是常数，就是O，1 交
32、替。这在强调低位随机性的应用中，是不令人满意的。为避免这种缺陷，可以选择模数21em，或者是选取m为小于2e的最大素数。对于模数21em的情况，(m od)nxm有快速实现方法（见附录）：注意上述算法中，第7 步其实是一个递归调用。整个算法中只有加减，位与，移位，比较和跳转操作。对于21em的情况也是类似的。3.5.2 乘数的选取模数m取得较大，序列的周期才可能较大。下面的定理1 指出了得到极大周期所应满足的条件：由,m a c和0 x所定义的线性同余序列有周期长度m，当且仅当：（1）c与m互素；（2）对于整除m的每个素数p，1ba是p的倍数；（3）如果0(m od 4)m，则0(m od 4
33、)b。该定理的证明过程见附录。在有些情况下，可能会利用0c（此时为乘同余法）来获得较快的生成速度。根据定理1,这时生成序列不可能达到极大周期聊。但仍然可以通过选择乘数a来使得序列周期尽可能地长。在生成公式(3-9)中，取0c，emp，则0(m od)nenxaxp（3-12）显然，周期是使得00(m od)Texaxp的最小正整数T。如果0 x与ep的最大公因子是fp，则由数论定理，得到:1(m od)Tefap (3-13)名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 41 页 -电子科技大学学士学位论文12 由数论欧拉定理可知：()1(m od)efpefap（3-14）
34、所以，T必是()efp的一个因子。欲使得T为最大，应当取T等于()efp.且若0 x与ep互素，则此时T等于1()(1)efeppp。并且当a是模m的一个本原元时，1(m od)Tam中T取得极大值()m。综上所述，得出下面的结论：当0c时，生成序列可能达到的极大周期等于模数m的欧拉函数()m，若满足：(1)初始值0 x与m互素；(2)乘数a是模m的一个本原元，则可以实现这一周期。3.5.3 线性同余法的缺陷线性同余序列众所周知的缺陷是其高维稀疏网格结构：当把相继的t 个随机数1(,)nnnmrrr，看作是m维空中上的一个点时，这些点只散布在m维空间的的少数几个超平面上，并形成稀疏的网格结构。
35、为说明线性同余法的问题，首先给出一个极简单的线性同余发生器：114(m od 17)(0,1,2,)nnxxn，其中/(0,1,2,)nnrxm n被看作是(0,1)上的随机数。当01x时，它产生周期为16 的如下序列 1，14，9，7，13，l2，15，6，l6，3，8，l0，4，5，2，ll，1容易看出，817nnxx，即其前半段与后半段的相关系数为一1，这便是同余发生器的长周期相关现象。Matteis Pagnuttir已从理论上证明了所有线性和非线性同余序列都存在长周期相关现象。在应用中，我们应特别警惕和回避这种现象。如果几个并行处理器分别使用同一个同余序列的不同段落，分割时就应避开具
36、有强相关的分点。3.5.4 广义线性同余法广义线性同余发生器(Generalized linear congruential generator,GLCG for short)是线性同余发生器的推广，其递推公式为:11(?,)(m od)(0,1,)nknnnkxfxxxmn（3-15）名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 41 页 -第 3 章 常见随机数生成法与比较13 其中f是11?,nnnkxxx的确定性函数。3.6 非线性同余法 80年代末开始，许多学者已经开始讨论非线性同余发生器(Nonlinear congruential generator,NLCG
37、for short)，其递推公式的一般形式为:1()(m od)(0,1,)nnnnxfxmnxrm（3-16）公式(3-17)中的 0,1,1nmxZm，而f是mZ上的一个整数函数。若()nnfxaxc，则公式(3-17)就是线性同余发生器。在非线性同余中f是mZ上的一个排列多项式，这时有(0),(1),(1)mfffmZ。下面介绍几种比较典型的非线性同余发生器:逆同余法、二次同余法、三次同余法和 BBS法。3.6.1 逆同余法逆同余发生器(Inversive congruential generator,ICG for short)，是非线性同余类中的最有前途的一种随机数发生器。其递推公式
38、为:nxmod(0,1,2.)nnnaxbmnxrm（3-17）其中对于(mcZm为素数），定义cc1 m od m且(mcZ若 c=0，定义c0），这时称c为 c 关于模 m 的乘法逆。逆同余法的主要优点在于能克服高维网格结构例如模为3121M的逆同余发生器可以通过直至3 02维的网格检验而线性同余发生器要保证10 维以内近似最优的网格结构都有困难(请参考 FishmanMoore，1986)然而逆同余法的周期不比线性同余法的长，Matteis-Pagnutti(1990)也从理论上证明了所有逆同余序列也都象线性同余序列那样存在长周期相关现象。另外，从应用上看，逆同余法的速度明显慢于线性同余
39、。名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 41 页 -电子科技大学学士学位论文14 3.6.2 二次同余法二次同余的生成表达式：21()(m o d)nnnxd xaxcm（3-18）上式产生的序列有周期长度m，当目仅当：(1)c与m互素，(2)对所有整除m的奇素数p，d和1a都是p的倍数；(3)如果m是 4 的倍数，则d是偶数，而且1(m od 4)da：如果m是 2 的倍数，则1(m od 2)da；(4)如果 m是 9 的倍数，则3(m od 9)dc.二次同余是一般线性同余的推广，由以上的结论可以看出，要获得极大周期m所需的条件限制并不比线性同余法更严格。3.6
40、.3 三次同余法三次同余的生成表达式：321()(m od)nnnnxaxbxcxdm（3-19）其中,a b c d均为正整数，且0a，m为正整数模，0 x为初始种子。数 a、c、m的取值满足一定条件时,才可得到较好结果。3.6.4 BBS 法BBS发生器是由 Blum和 Shub共同提出的一种随机数发生器。其递推公式2i1ixxm od mi0,1,2.（3-20）3.7 取小数法这种方法不能直接用公式表达,其原理是将前一次随机数平方后的数,取其小名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 41 页 -第 3 章 常见随机数生成法与比较15 数点后第一个非零数字后面的尾
41、数作为下一个所求的随机数。3.8 常见随机数生成法的比较前面介绍各种随机数生成法时，已经大概介绍了下各种方法的优缺点。现在再简要比较下各种随机数生成法的优缺点。平方取中法的优点是计算简单,计算机上易于实现，内存占用少，缺点是种子的选择很重要,对初始数据的依赖很大，否则很难保证有足够长的周期,而且容易出现退化现象（以后的随机数为同一常数或为 0）。斐波那契法的优点是计算简单,计算速度很快，周期较长且达到满周期，可证明为1.5 m。缺点序列中数重复出现，独立性较差。此发生器没有乘法运算，产生速度快但是它存在着令人不能容忍的不居中现象，即由前两个数得到的第三个数要不是同时大于就是同时小于前二者而永不
42、居中。此序列的另一个缺点是显著的序列相关，即取小值的数后面出现也取小值的趋势。所有这些都说明它不是一个好的随机数序列。移位法运算速度快，但是对初始值的依赖性也很大，一般地初始值不能取得太小，选得不好会使伪随机数列长度较短。同时(1)mm维均匀随机向量相关性大，即独立性较差，存在稀疏网格，最后随机数序列周期T与计算机的字长有关。线性同余法是一种较好的方法,目前很多仿真语言中使用的就是这种方法。其缺点是高维稀疏网格结构，有长周期相关现象，相对而言其计算要复杂些,而且只有公式中的常数,ma c的取值满足一定条件时,才可得到较好结果。非线性及逆同余的缺陷是长周期相关，周期依赖机器字长，产生效率低。取小
43、数法的优缺点类似于平方取中法,而且要求种子一般应取纯小数,并且数字位要尽量多。名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 41 页 -电子科技大学学士学位论文16 第4章 随机数生成法的统计和检验随机数的好坏如何，即它们的性质究竟与真正的0,1区间上的均匀分布的随机变量的简单随机样本的性质有无显著差异，是一个很重要的问题。如果有显著差异，则以这种随机数发生器产生的随机数为基础的随机变量所抽得的样本，实际上将不能反映该随机变量的性质，从而所得随机模拟的最后的结果将是不可靠的。因此对随机数进行检验，将是很重要的工作。在进行统计检验之前，下面首先简单介绍一些统计检验的基础知识。4
44、.1 检验类型一般情况下有两种不同的检验方法:(1)经验检验:经验检验是一种统计检验，它是以发生器产生的均匀随机数序列ix为基础的，根据0,1区间上均匀总体简单随机样本iu的性质，如特征向量、均匀性、随机性等，研究我们产生的随机数序列ix的相应性质，进行比较、鉴别、视其差异是否显著，决定取舍。(2)理论检验:理论检验从统计意义上讲并不是一种检验。它是一种综合的方法来评估发生器的数值参数，而根本不必产生任何随机数序列ix，即它是一种理论上的研究。本章主要介绍一些经验检验，对于理论检验由于涉及过多的专门学科的知识，数学上相当困难的，本章不再给予讨论。4.2 统计检验的一般方法统计检验的一般方法有以
45、下几种：(1)参数检验:均匀随机数的参数检验是检验由某个发生器产生的随机数序列ix的均值、方差和各阶矩等与均匀分布的理论值是否有显著的差异。(2)均匀性检验:随机数的均匀性检验又称频率检验，它是来检验由某个发生器产随机数序列ix时，是否均匀地分布在区间0,1上。也就是检验经验频率与理论频率的差异是否显著。(3)独立性检验:独立性检验主要是检验随机数序列12,nxxx之间的统计相关性是否显著。即判别每个数的出现是否与其前后各数独立无关。名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 41 页 -第 4 章 随机数生成法的统计和检验17（4）无连贯性检验：将依次出现的N伪随机数，按
46、其大小分为两类或者k类，则各类数的出现是否有连贯现象。对于参数检验，由于随机数服从标准均匀分布(0,1)U,则其均值和方差的理论值分别为：20.5,1/12（4-1）当样本容量充分大时，可用正态分布进行检验。利用2拟合优度检验(取 10个区间)可以检验所产生的随机样本的总体分布是否为均匀分布。利用游程检验法检验随机样本的独立性，其中游程是由连续0 或者 1 组成的序列，并且其前后元素与游程的元素不同游程数目为序列长度的一半产生的随机序列较好。4.2.1 参数检验若随机变量R0,1U，则2111,2123ERV a rRER，若12,.,nRRR是均匀总体的简单随机样本，即12,.,nRRR相互
47、独立同0,1U分布。记11niiRRn，2211niiRRn，221112niiisRn则有：12ER，11 2V arRn；213ER，2445V a rRn；211 2Es，2118 0V a rsn。设12,.,nrrr是某个发生器产生的随机数。首先对特征量作统计检验。在ir是均匀总体的 简单随机样本的假设下，统计量：名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 41 页 -电子科技大学学士学位论文18 1122irErunrVarr22221451323rnurVarr2232111218012sunsVars渐进服从0,1N。给定显著水平后，查标准正态数值表得：:,
48、0,1iiPuuN，否定域1,2,3iiWui。由随机数列ir计算123,uuu的值，若iu，则认为产生的随机数序列的特征量与均匀总体的特征量没有显著差异；否则由于ir得特征量与均匀总体特征量有显著差异，故不能认为ir是均匀总体的简单样本。4.2.2 均匀性检验均匀性检验中常用的方法有:卡方检验、柯氏检验和序列检验。4.2.3 重要分布（1）二项分布:如果随机变量x的所有可能取值为0,1,2,kn,且x取值k的概率为(1)kknkknpCpp，0,1,2,kn(4-2)则称 x 服从参数为 n,p 的二项分布，记为,xBnp。当 k 取值仅为 0,1 时，又称 x 服从 0-1 分布或两点分布
49、。（2）正态分布：如果随机变量 X的概率密度函数为：221ex p22xufx（4-3）名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 41 页 -第 4 章 随机数生成法的统计和检验19 则称随机变量X 服从参数为2,的正态分布，记为2,XN。如果01，则称 X服从正态分布，记为2XN，。其分布函数记为：2/212zuzedu（4-4）(3)2分布设12,.,nxxx是来自于标准正态总体N(0,1)的独立样本，则由它们构造的统计量21niiXx服从自由度为 n 的2分布。自由度为 n 的2分布的概率密度函数为：/2 1/2/2102/2,00nxnxexnfx nx（4-5）
50、其中伽玛函数10zxzxedx，而,0aa。对一般的伽玛函数，有1,atxa xtedt。特别地，对于a 为整数 n 的情况，有:10,1!knxkxn xnek (4-6)4.2.4 重要定理（1）Pearson 定理利用总体的样本值1,2,.,nx xx来检验总体的分布函数是否为F(x)。先设定原假设0H:X 的分布函数为F（x），F（x）为某已知分布函数。取k-1 个点，满足：121.kttt将实数轴分为 k 个区间：1121,.,ktttt。设样 本 值12,.nxxx中 落 入 第 i个 区间1,iitt内 的 个 数 为tv，其 相 对 频数 为/,1ivnik。如果原假设0H成立