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

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