混合同余法产生均匀分布随机数产生方法总结.docx

混合同余法产生均匀分布随机数产生方法总结
主要学习混合同余法产生各种分布的随机数的方法，见参考文献[1, 2]，重点参考[2]。其中要注意混合同余法产生随机数的参数的选取。
1 混合同余法产生均匀分布的随机数
1.1 混合同余法
通过同余运算生成伪随机数的方法称为同余法，常用的同余法包括加同余法、乘同余法、混合同余法、除同余法。其中乘同余法和混合同余法的性能更好，有速度快、内存省、周期长、统计特性好等优点。混合同余法是Lehmer在1951年提出的，其迭代公式为[2]：
(1.1)
(1.2)
公式、中，mod表示求余函数，均为正整数。其中是模数，是乘数，是增量，为初始值，当时，称此算法为乘同余法；若，则称算法为混合同余法，当取不为零的适当数值时，有一些优点，但优点并不突出，故常取。是在内服从均匀分布的随机变量，则是在内服从均匀分布的随机变量。式中的取值并不是随意的，模大小是发生器周期长短的主要标志，常见有为素数，取为的原根，则周期。试验统计表明，用以下参数进行混合同余法产生的随机序列的统计特性较好：
(1.3)
(1.4)
(1.5)
(1.6)
(1.7)
(1.8)
(1.9)
(1.10)
(1.11)
(1.12)
(1.13)
在式~中，16807、32719、1220703125都是的原根。
混合同余法产生的随机序列具有以下特点：
Ø 重复周期较小，由于取值在内，其周期，受的值得影响，在编程实现时，浮点运算也会对产生影响
Ø 用此方法产生的随机序列，在一个周期内任意两个随机数不可能相等，这往往与实际情况不相符
经Hull和Dobell证明，只有满足以下一些关系才能实现周期最大化，即，条件如下：
Ø 与互质（或互素，即它们的最大公约数为1）
Ø 设为某一质数，分别能被和4整除，且能被和4整除
产生具有最大周期的伪随机序列的混合同余法算法为：
(1.14)
(1.15)
由于时，只有一个素数因子2，且4也是的因子，此时，正好满足了的第二个条件；而此时刚好与互质，即满足的第一个条件。
1.2 改进的混合同余法
改进的混合同余法的迭代公式如下[2]：
(1.16)
(1.17)
改进的混合同余法具有以下特点：
Ø 比混合同余法产生的周期长，
Ø 允许某个伪随机数重复发生，且重复发生的次数为
Ø 伪随机序列的周期一般与初始值的选取无关，只有极个别的情况除外
1.3 原根相关知识
1.3.1 欧拉函数
在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。
1.3.2 原根
定义1 设m > 1，(a, m) = 1，则使
(1.18)
成立的最小的正整数r，称为a对模m的指数，记为dm(a)，在不致误会的情况下，简记为d(a)。
由Euler定理，当r = j(m)时式(1)成立，因此，恒有dm(a) £ j(m)。
若a º b (mod m)，(a, m) = 1，则显然有dm(a) = dm(b)。
定义2 若dm(a) = j(m)，则称a是模m的原根。
例如，当m = 7时，因为
21 º 2，22 º 4，23 º 1 (mod 7)，
所以d7(2) = 3。又因为
31 º 3，32 º 2，33 º 6，34 º 4，35 º 5，36 º 1 (mod 7)，
所以d7(3) = 6 = j(7)，3是模7的原根。
以后，在谈到a对模m的指数时，总假定m > 1，(a, m) = 1。

参考文献
[1] 吴飞. 产生随机数的几种方法及其应用[J]. 数值计算与计算机应用, 2006, (01): 48-51.
[2] 郭凤鸣. 一种生成大周期伪随机数的新算法——改进的混合同余法[J]. 地球科学, 1992, (06): 733-738.