摘 要
摘要
本文着重讨论了随机数生成方法、随机数生成法比较以及检验生成的随机序列的随机性的方法。
在随机序列生成方面，本文讨论了平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、取小数法等，并比较了各方法的优劣性。
在统计检验方面，介绍了统计检验的方法，并用其检验几种随机数生成器生成的随机数的随机性。
最后介绍了两种新的随机数生成法，并统计检验了生成随机序列的随机性。
关键词：随机数，随机数生成法，统计检验
I
ABSTRACT
ABSTRACT
This article focuses on methods 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 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 statistical tests of randomness to generate a random sequence.
Key Words: random number，random number generator，statistical test
II
目录
目录
第1章 引言 ......................................................................................................................... 1 1.1 课题背景 ............................................................................................................ 1 1.2 课题的价值及意义 ............................................................................................ 1 1.3 课题的难点、重点、核心问题及方向 ............................................................ 1 第2章
随机数 ............................................................................................................. 3 2.1 基本概念 ........................................................................................................... 3 2.2 产生随机数的一般方法 ................................................................................... 3 2.3 随机数生成的数学方法 ................................................................................... 4 2.4 产生随机数的方法种类 ................................................................................... 5 2.5 随机数的应用 ................................................................................................... 6 第3章
常见随机数生成法与比较 ............................................................................. 7 3.1.1 迭代算法 .................................................................................................. 7 3.1.2 平方取中法的优缺点 .............................................................................. 7 3.2 斐波那契(Fibonacci)法 ...................................................................................... 8 3.3 滞后斐波那契(Fibonacci)法 .............................................................................. 9 3.4 移位法 ................................................................................................................ 9 3.5 线性同余法 ...................................................................................................... 10
3.5.1 模数的选取 ............................................................................................ 10 3.5.2 乘数的选取 ............................................................................................. 11 3.5.3 线性同余法的缺陷 ................................................................................ 12 3.5.4 广义线性同余法 .................................................................................... 12 3.6 非线性同余法 .................................................................................................. 13
3.6.1 逆同余法 ................................................................................................ 13 3.6.2 二次同余法 ............................................................................................ 14 3.6.3 三次同余法 ............................................................................................ 14 3.6.4 BBS法 ..................................................................................................... 14 3.7 取小数法 .......................................................................................................... 14
III
3.1 平方取中法 ........................................................................................................ 7
目录
3.8 常见随机数生成法的比较 .............................................................................. 15 第4章
随机数生成法的统计和检验 ....................................................................... 16 4.1 检验类型 .......................................................................................................... 16 4.2 统计检验的一般方法 ...................................................................................... 16
4.2.1 参数检验 ................................................................................................ 17 4.2.2 均匀性检验 ............................................................................................ 18 4.2.3 重要分布 ................................................................................................ 18 4.2.4 重要定理 ................................................................................................ 19 4.2.5 卡方检验 ................................................................................................ 20 4.2.6 柯氏检验 ................................................................................................ 20 4.2.7 序列检验 ................................................................................................ 21 4.3 独立性检验 ...................................................................................................... 22 4.4 对线性同余法和取小数法进行随机性检验 .................................................. 22 第5章
新的随机数生成法 ....................................................................................... 24 5.1 开方取小数法 .................................................................................................. 24 5.2 一种混合型随机数发生器 .............................................................................. 28
5.2.1 超素数长周期法 .................................................................................... 28 5.2.2 组合发生器的研究 ................................................................................ 30 5.2.3 随机数算法统计检验结果 .................................................................... 30
结束语 ............................................................................................................................ 32 参考文献 ........................................................................................................................ 33 致谢 ................................................................................................................................ 34 外文资料原文 ................................................................................................................ 35 翻译文稿 ........................................................................................................................ 37
IV
第1章 引言
第1章 引言
1.1 课题背景
随机数(随机序列)在不同的领域有许多不同类型的应用。如雷达中的测距信号，遥控遥测中的测控信号，数字通信中的群同步和加扰解扰信号，无线通信码分多址系统中的扩频信号等都要用到随机序列。在用计算机的教学与学习中，也经常需要用到随机数，比如，数据结构中关于一个数据的存储地址，在各种程序设计语言学习中遇到的随机量的生成，图像处理中遇到的随机色彩的选择等，枚不胜举，随机数在计算机的应用中就显得格外重要。尤其在仿真等领域，更对随
机数的产生提出了较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。现实中，用投色子计数的方法产生真正的随机数，但电脑若也这样做，将会占用大量内存；虽然用噪声发生器或放射性物质也可产生真正的随机数，但操作不可重复。而用数学方法产生随机数则最适合计算机，这就是“伪随机数”。我们需要的随机数序列应具有非退化性，周期长，相关系数小等优点。
迄今为止，研究人员提出了许多不同的随机数生成方法，如平方取中法，同余法，斐波那契序列变形法，混沌序列法，利用系统时间和热噪声等等。随着新的随机数性能测试方法的提出，已经证明其中的某些生成方法有其固有的缺陷。 同时对测试方法的研究也是一个不断发展的过程。
1.2 课题的价值及意义
由于现在对随机数的公认定义中，只给出了随机数的性质描述，而没有给出其生成方法，同时现有的所有检测方法也只是给出了一些必要而非充分的条件。因此，随机数的生成及其性能检测方法，都有待于进一步的研究。具体的应用环境不同，对随机数发生器的性能要求就不一样，而不同的随机数发生器产生的随机数的性质必然不一样。为了能对一个随机数发生器的性能做一个比较全面和客观的评价，需要对不同的测试方法进行研究，讨论其测试目的和测试依据。本课题主要是讨论随机数生成法，随机数生成法比较以及随机数的检测统计，从上面分析看出，本课题是很有意义和开拓性的工作。
1.3 课题的难点、重点、核心问题及方向
本课题的核心问题是随机数生成法、随机数生成法比较以及随机数的统计检验。本课题的主要工作内容如下：
（1）介绍几种常见的随机数生成法，并比较了各种随机数生成法的优劣；（2）
1
电子科技大学学士学位论文
介绍统计检验的理论，并对几种随机数生成法进行了统计检验；
（3）介绍新的随机数生成法，并对随机数进行统计检验。
2
第2章 随机数
第2章 随机数
在用计算机的教学与学习中，经常需要用到随机数，比如，数据结构中关于一个数据的存储地址，在各种程序设计语言学习中遇到的随机量的生成，图像处理中遇到的随机色彩的选择等，不胜枚举，随机数在计算机的应用中就显得格外
重要。尤其在仿真等领域对随机数的产生提出了更较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。现实中，用投色子计数的方法产生真正的随机数，但电脑若也这样做，将会占用大量内存；虽然用噪声发生器或放射性物质也可产生真正的随机数，但操作不可重复。而用数学方法产生随机数则最适合计算机，这就是“伪随机数”。我们需要的随机数序列应具有非退化性，周期长，相关系数小等优点。
2.1 基本概念
在密码学中，对于一个随机序列的定义如下： (1) 看起来是随机的。 (2) 这个序列是不可预测的。 (3) 这个序列是不能重复产生的。
随机变量?的抽样序列?1,?2,??n,?，称为随机数列。如果随机变量?是均匀分布的，则?的抽样序列?,?,??,?，称为均匀随机数列；如果随机变量? 是
12n正态分布的随机变量则称其抽样序列为正态随机数列。
随机序列具有以下性质：
（1)等分布性：随机序列的分布特性是等概分布，或称为一致分布。即是说序列中每个元素出现的概率都是相等的。
（2)独立性：随机序列的各个元素之间是相互独立的。 （3)不可预测性：该性质可由等分布性和相互独立性推出。
（4)白噪声谱特性：由独立性可知，随机序列的自相关函数为?函数。
2.2 产生随机数的一般方法
随机数产生方法的研究己经有很长的历史，至今仍有统计学者继续研究随机数产生的方法和理论。
产生随机数的一般方法:
(1)手工方法:这是随机数产生的最早方法，即采用抽签、掷筛子、抽牌、摇号或从搅乱的罐子中取带数字的球等方法。
(2)随机数表方法:Monte-Carlo方法的出现，需要大量的随机数，显然用手工的方法不能满足模拟计算的需要。1927年Tipett造出了具有4万个随机数字的表;1939
3
电子科技大学学士学位论文
年Kendell和Babington-Smith用高速转盘建立了有+万个数字的随机数表;兰德(Rand)公司利用电子装置产生了含有一百万个数字的随机数表。在电子计算机产生之前人们就是利用这些随机数表进行统计模拟计算。
(3)物理方法:随着计算机和模拟方法的广泛应用，用计算机产生随机数成为新的课题。在计算机上安装一台物理随机数发生器，把具有随机性质的物理过程变换为随机数，使用物理随机数发生器在计算机上可以得到真正的随机数，随机性和均匀性都是很好的，而且是取之不尽用之不竭的。但是此方法也有一些缺点，其中最重要的是我们不能产生同原来完全相同的随机数，对计算结果不能进行复算检查;加上物理随机数发生器的稳定性经常需要进行检查和维修，因而大大降低了这种方法的使用价值。
(4)数学方法:它是利用数学递推公式来产生随机数的;它是目前使用最广泛、发展很快的一类方法;它的特点是占用内存少、速度快又便于计算。
本文主要是介绍用数学方法来产生随机数的算法，即各种各样的随机数发生器。
2.3 随机数生成的数学方法
用数学方法产生随机数，就是利用计算机能直接进行算术运算或逻辑运算的特点，选取一个适宜的数学递推公式rn?m?f(rn,?,rn?m?1)，利用计算程序，按递推公式对数字进行加工处理，把0,1,?,bm?1或其部分数字的自然顺序打乱，产生具有均匀总体、简单子样统计性质的随机数，这里一般m取较小的正整数，b为机器的字长。
用数学方法产生的随机数的速度快，占用内存少，对模拟的问题可以进行复算检查，一般还有较好的统计性质．但是，由于计算机只能表示有限位不同的数，严格说，在计算机上不能产生真正连续分布的随机数，只能产生离散分布的随机数来代替连续分布的随机数．另外，计算机上用数学方法产生随机数，是根据确定的算法推算出来的，因此严格说来，用数学方法在计算机上产生的“随机数”不能说是真正的随机数，故一般称之为“伪随机数”。随机数生成方式有真随机和伪随机两种。真随机数生成法满足以上关于随机序列定义的所有三点要求，伪随机数生成法只满足前两点要求。不过对这些伪随机数，只要通过统计检验符合一些统计要求，如均匀性、随机性等，就可以作为真正的随机数来使用。所以本文在后面章节将会介绍随机数、随机数生成法、随机数生成法比较以及随机数的统计检验。
4
第2章 随机数
在计算机上用数学方法产生随机数的一般要求如下：
1)产生的随机数列要有均匀性、抽样的随机性、试验的独立性和前后的一致性； 2)产生的随机数列要有足够长的周期，以满足模拟实际问题的要求； 3)产生随机数的速度要快，占用的内存少。 数学方法生成随机数的过程如下： (1) 找到一个数学模型或算法。 (2) 设置其中参数的值。
(3) 通过某种运算产生种子即第一个随机数。 (4) 然后在产生的种子的前提下，生成第二个随机数。
通过同样的步骤，就产生了一个随机数序列。从上可以看出，计算机中伪随机数序列的产生有两大要素，一是产生随机数序列的初始值，称之为随机种子；二是产生随机数的计算方法，即随机函数。计算机的伪随机数序列是由随机种子根据一定的计算方法计算递推出来的序列。伪随机数生成器将作为 “种子”的数当作初始整数传给函数。这粒种子会使这个球(生成伪随机数)一直滚下去。伪随机数生成器的结果仅仅是不可预测。由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定，最终，该种子决定了一切。如果知道用于计算任何一个值的那个整数，那么就可以算出这个生成器返回的下一个值。结果，伪随机数生成器是一个生成完全可预料序列的确定性程序。只要计算方法一定，随机种子一定，那么程序每次产生的随机数序列就是固定的。
通常而言，计算方法是不容易改变的，而随机种子是可以随时改变的，程序每次运行时可赋予不同的随机种子从而得到不同的序列。
2.4 产生随机数的方法种类
由于产生随机数的计算方法（随机函数）不同，现在大体有以下几种常见方法：平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、混沌序列法、取小数法等。一个好的随机数发生器应当具备以下几点条件:
(1)产生的随机数序列要具有均匀总体随机样本的统计性质，如分布的均匀性，抽样的随机性，数列间的独立性等等。(经验检验)
(2)产生的随机数序列要具有较好的理论支持(或具有好的格结构)，如分布的谱检验(Spectral test)和高维分布检验(k-distribution test)。(理论检验)
(3)产生的随机数序列要有足够长的周期，以满足模拟计算的需要。
5
电子科技大学学士学位论文
(4)产生的随机数序列的速度快，占用计算机的内存少，具有完全可重复性。 随着计算机运算速度的不断提高，存储容量和字长的不断扩大，(3)和((4)两点一般都能满足;至于条件(2)属于理论方面的问题，由于涉及到很多数论等基础数学方面的内容，本文不做过多的研究。因此，关键是如何构造满足(1)的随机数发生器，即做大量的统计检验工作。下面章节将详细介绍各方法，并分析比较各方法的优缺点，最后对各方法做统计检验工作。
2.5 随机数的应用
随机序列有许多不同类型的应用。诸如用于仿真各种自然现象，用于检验计算机程序设计中的随机化算法，甚至有时候被人们用来做决策。同时随着计算机技术、通信技术的充分发展，信息在传递、处理、存储过程中的安全问题已引起了人们的广泛关注．信息安全领域内的核心问题之一就是如何制作高质量的随机数发生器和产生随机数的方法。现在，随机数已广泛应用于在密码算法方面、安全协议方面、数字水印方面等信息安全领域
在很多情况下，系统决策需要进行多次仿真比较才能确定，重现性非常必要。因此，在计算机上生成伪随机数及对伪随机数进行检验的问题就受到人们的重视。模拟计算表明，通过改进伪随机数的品质，可使计算机仿真结果的有效性得到明显提高，在有些情况下甚至可使仿真结果的数值相对误差缩小为原来的1/10或更小。因此，进行伪随机数发生器的研究，具有重要的理论意义和应用价值。
6
第3章 常见随机数生成法与比较
第3章 常见随机数生成法与比较
由于产生随机数的计算方法（随机函数）不同，现在大体有以下几种常见方法：平方取中法、斐波那契法、滞后斐波那契法、移位法、线性同余法、非线性同余法、混沌序列法、取小数法等。
3.1 平方取中法
产生伪随机数列最早的方法是平方取中法，它是由冯·诺依曼提出的。 3.1.1 迭代算法
此法开始取一个2s位的整数，称为种子，将其平方，得4s位整数(不足4s位的高位补0)，然后取此4s位的中间2s位作为下一个种子数，重复上述过程，即可得到一系列随机数。平方取中法的递推公式为:
2 xn?1?[xn /10s](mod102s) （3-1）
产生伪随机数列：
rn?xn/102s （3-2）
3.1.2 平方取中法的优缺点
平方取中法的优点为在计算机上易于实现，内存占用少，但仍存在对小数目偏倚的现象，均匀性不好，对初始数据的依赖很大，数列的长度和周期难以确定，很容易出现重复元素的短循环，而且，一旦某个元素是0，则后面所有的元素都将是0 。
如果生成的序列中，有从最高位开始连续s个0的数，则产生的序列会逐渐退
s2s化为0。这是因为在十进制表示的情况下：rn?10,rn?rn?10，则由（3-1）可得rn?1?rn。
或者生成的序列中，有从最低位起至少连续的??s???1个0的数，则产生的序列也会逐渐退化到0。这是因为：如果生成序列中rn满足上述条件， 则rn2从末位起至少有2s?2个0，即是说rn?i末位的0比rn?i?1末位的0多，从而逐渐退化为全0。
7
电子科技大学学士学位论文
当生成的序列中，有从最低位起有连续的s个0的数，则生成的序列元素，从最低位起，有一半的位为0。它的最长周期已由2s退化为s，这样的数，已不适合再称为伪随机数。
平方取中法有一些变形和推广。其中之一就是：后一个序列元素不再只依赖于前一个元素，而是依赖于前几个，甚至是不相邻的几个序列元素。这种变形和推广使得序列的周期长度通常大于2s，但产生的序列的随机性需要经过检验。
另一种就是对平方取中法进行改进的方法是，乘积取中法，如果要产生具有1O进制2s位的伪随机数列，任取两个初始随机数x0,x1，用递推公式：
xn?2?[xn?1xn/10s](mod102s) （3-3）
产生伪随机数列：
rn?xn/102s （3-4）
乘积取中法与平方取中法比较，从产生的伪随机数列长度及均匀性方面都有改善，但是数列长度还是不够，而且对初始值的依赖性很大。
3.2 斐波那契(Fibonacci)法
斐波那契法是基于Fibonacci序列，其递推公式为:
?xn?2?(xn?1?xn)modm? ? (n?1,2,?) （3-5）xnrn??m?
显然，斐波那契法有两个初始种子x0和x1。方法的最大特点就是计算速度很快，且达到满周期。但是序列中数重复出现，独立性较差。此发生器没有乘法运算，产生速度快．但是它存在着令人不能容忍的不居中现象，即由前两个数得到的第三个数要不是同时大于就是同时小于前二者而永不居中。此序列的另一个缺点是显著的序列相关，即取小值的数后面出现也取小值的趋势。所有这些都说明它不是一个好的随机数序列。
8
第3章 常见随机数生成法与比较
3.3 滞后斐波那契(Fibonacci)法
滞后的斐波那契法是斐波那契法的推广，目前存在很多种形式。下面仅仅给出一种比较有名的方法，其递推公式为:
?xn?(xn?p?xn?q)modm? ? (n?0,1,?) （3-6）xnrn??m?
其中p?q?0，初始种子为(x?1,x?2,?,x?p)。
3.4 移位法
计算机善于进行移位等逻辑运算，应用计算机的这个特点有一类产生伪随机数列的方法，该方法称为移位法。本方法是关于平方取中法的一种改进形式，它是移位运算与指令相加运算相结合的迭代过程。
它的思想是：首先选取一个初始值x0，使之左右移位，分别为x01和x02，然后指令相加得x1，再对x1进行上述过程，如此重复下去，便可得随机数序列。对于字长为32位的计算机，这一算法的递推公式为：
xn?1?27xn?2?7xn(mod232) （3-7）
产生伪随机数列：
rn?xn/232 （3-8）
移位法运算速度快，但是对初始值的依赖性也很大，一般地初始值不能取得太小，选得不好会使伪随机数列长度较短。同时m(m?1)维均匀随机向量相关性大，即独立性较差。最后随机数序列周期T与计算机的字长有关。
9
电子科技大学学士学位论文
3.5 线性同余法
同余法(Linear Congruential Generator, LCG for short)是Lehmer于1951年提出来的，此方法是利用数论中的同余运算原理来产生随机数，有线性同余法、非线性同余法等，其中线性同余法法又分为加同余法、乘同余法以及混合同余法。同余法是现在发展迅速且使用普遍的方法之一。首先介绍下线同余法。
线性同余法的递推式为：
xn?1?axn?c(modm) (n?0,1,2,?) （3-9）
式中参数a,c和m分别称为乘、增量和模，x0为种子。如果这些参数和种子(初值)
x都指定序列也就确定下来了。通常取 rn?n(n?0,1,2,?)作为区间(O，1)上均匀
m分布U(0,1)的随机数。从上可以看出当c?0，为乘同余法；当a?1,c?0时，为加同余法，否则称为混合同余法。按惯例，当强调使用某方法产生随机数时，常使用某方法(随机数)发生器的称呼。 线性同余法有如下特点: (1)0?xi?m?1。
(2)适当选取m,a,c可使xi循环，无论x0取何值，其循环顺序相同，其循环 周期称为发生器周期，记为T。若T?m，则称之为满周期。
(3)适当选取m,a,c，可保证xi在[[0, 1〕区间上一个周期内每个整数正好出现一次，从而保证了均匀性。
(4)为提高ri的均匀性，要求加大m。 下面讨论下线性同余中参数的选取。 3.5.1 模数的选取
从线性同余的生成公式中可以看到，生成序列xn的最长周期不可能超过m。为得到较长的周期，需要选择较大m值。考虑m的另一个方面是实现时的生成速度。
在二进制计算机上，进行模运算，最好选择模数m?2e的形式。这样模运算，只需要进行位与操作就可以实现了。但是这种简单的选择，在某些应用中，却不是令人满意的。这里，假设选取m?2e，则d?24是m的一个因子。这里d的指数选取为4是因为我们假设只考察生成序列元素xn的最低四个比特位的规律。
10
第3章 常见随机数生成法与比较
yn?xn(modd) （3-10）
yn?1?xn?1(modd)?(axn?c)(modd)?(ayn?c)(modd) （3-11）
可以看到，由序列xn的各元素低三比特位组成的序列是一个周期更短的同余序列。它的最长周期为16。类似的，xn低三位的最长周期为8，xn低五位的最长周期为32，等等。xn的最低位不是常数，就是O，1交替。这在强调低位随机性的应用中，是不令人满意的。
为避免这种缺陷，可以选择模数m?2e?1，或者是选取m为小于2e的最 大素数。对于模数m?2e?1的情况，(xnmodm)有快速实现方法（见附录）：
注意上述算法中，第7步其实是一个递归调用。整个算法中只有加减，位与，移位，比较和跳转操作。对于m?2e?1的情况也是类似的。 3.5.2 乘数的选取
模数m取得较大，序列的周期才可能较大。下面的定理1指出了得到极 大周期所应满足的条件：
由m,a,c和x0所定义的线性同余序列有周期长度m，当且仅当： （1）c与m互素；
（2）对于整除m的每个素数p，b?a?1是p的倍数； （3）如果m?0(mod4)，则b?0(mod4)。 该定理的证明过程见附录。
在有些情况下，可能会利用c?0（此时为乘同余法）来获得较快的生成速度。根据定理1,这时生成序列不可能达到极大周期聊。但仍然可以通过选择乘数a来使得序列周期尽可能地长。
在生成公式(3-9)中，取c?0，m?pe，则
xn?anx0(modpe) （3-12）
显然，周期是使得x0?aTx0(modpe)的最小正整数T。如果x0与pe的最大公因子是pf，则由数论定理，得到:
aT?1(modpe?f) (3-13)
11
电子科技大学学士学位论文
由数论欧拉定理可知：
a?(pe?f) ?1(modpe?f) （3-14）
所以，T必是?(pe?f)的一个因子。欲使得T为最大，应当取T等于?(pe?f).且若x0与pe互素，则此时T等于?(pe?f)?pe?1(p?1) 。并且当a是模m的一个本原元时，aT?1(modm)中T取得极大值?(m)。
综上所述，得出下面的结论：
当c?0时，生成序列可能达到的极大周期等于模数m的欧拉函数?(m)，若满足：
(1)初始值x0与m互素；
(2)乘数 a是模m的一个本原元，则可以实现这一周期。 3.5.3 线性同余法的缺陷
线性同余序列众所周知的缺陷是其高维稀疏网格结构：当把相继的t个随机数(rn,rn?1,?,rn?m)，看作是m维空中上的一个点时，这些点只散布在m维空间的的少数几个超平面上，并形成稀疏的网格结构。
为说明线性同余法的问题，首先给出一个极简单的线性同余发生器： xn?1?14xn(mod17) (n?0,1,2,?)，其中 rn?xn/m(n?0,1,2,被看作是?)(0,1)上的随机数。当x0?1时，它产生周期为16的如下序列1，14，9，7，13，
l2，15，6，l6，3，8，l0，4，5，2，ll，1．容易看出，xn?17?x8?n，即其前半段与后半段的相关系数为一1，这便是同余发生器的长周期相关现象。Matteis Pagnuttir已从理论上证明了所有线性和非线性同余序列都存在长周期相关现象。在应用中，我们应特别警惕和回避这种现象。如果几个并行处理器分别使用同一个同余序列的不同段落，分割时就应避开具有强相关的分点。 3.5.4 广义线性同余法
广义线性同余发生器(Generalized linear congruential generator, GLCG for short)是线性同余发生器的推广，其递推公式为:
xn?k?f( xn?,xn?1,?,xn?k?1)(modm) (n?0,1,?) （3-15）
12
第3章 常见随机数生成法与比较
其中f是xn?,xn?1,?,xn?k?1的确定性函数。
3.6 非线性同余法
80年代末开始，许多学者已经开始讨论非线性同余发生器(Nonlinear congruential generator, NLCG for short)，其递推公式的一般形式为:
?xn?1?f(xn)(modm)? ? (n?0,1,?) （3-16）xnrn??m?
公式(3-17)中的xn?Zm?{0,1，而f是Zm上的一个整数函数。若?,m?1}f(xn)?axn?c，则公式(3-17)就是线性同余发生器。在非线性同余中f是Zm上 的一个排列多项式，这时有{f(0),f(1),?,f(m?1)}?Zm。
下面介绍几种比较典型的非线性同余发生器:逆同余法、二次同余法、三次同余法和BBS法。 3.6.1 逆同余法
逆同余发生器(Inversive congruential generator, ICG for short)，是非线性同余类中的最有前途的一种随机数发生器。其递推公式为:
?xn??axn?b?modm? (n?0,1,2...) （3-17）?xnrn??m?
其中对于c?Zm(m为素数），定义cc?1modm且c?Zm(若c=0，定义c?0），这时称c为c关于模m的乘法逆。
逆同余法的主要优点在于能克服高维网格结构．例如模为M?231?1的逆同余发生器可以通过直至230维的网格检验．而线性同余发生器要保证10维以内近似最优的网格结构都有困难(请参考Fishman—Moore，1986)．
然而逆同余法的周期不比线性同余法的长，Matteis-Pagnutti(1990)也从理论上证明了所有逆同余序列也都象线性同余序列那样存在长周期相关现象。另外，从应用上看，逆同余法的速度明显慢于线性同余。
13
电子科技大学学士学位论文
3.6.2 二次同余法
二次同余的生成表达式：
2 xn?1?(dxn?axn?c)(modm) （3-18）
上式产生的序列有周期长度m，当目仅当： (1)c与m互素，
(2)对所有整除m的奇素数p，d和a?1都是p的倍数；
(3)如果m是4的倍数，则d是偶数，而且d?a?1(mod4)：如果m是 2的倍数，则d?a?1(mod2)；
(4)如果m是9的倍数，则d?3c(mod9).
二次同余是一般线性同余的推广，由以上的结论可以看出，要获得极大 周期m所需的条件限制并不比线性同余法更严格。 3.6.3 三次同余法
三次同余的生成表达式：
32 xn?1?(axn ?bxn?cxn?d)(modm) （3-19）
其中a,b,c,d均为正整数，且a?0，m为正整数模，x0为初始种子。 数a、c、m的取值满足一定条件时,才可得到较好结果。 3.6.4 BBS法
BBS发生器是由Blum和Shub共同提出的一种随机数发生器。其递推公式
（3-20） xi?1?xi2modm?i?0,1,2...?
3.7 取小数法
这种方法不能直接用公式表达,其原理是将前一次随机数平方后的数,取其小
14
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库随机数生成方法、随机数生成法比较以及检验生成的随机序列的随机在线全文阅读。
相关推荐：
