线性同余发生器是当前应用比较多的一种随机数发生器,其简称为LCG(Linear Congruence Generator)或者也叫做LCG方法。于1951年由Lehmer提出,也被称作同余发生器,因为它是利用的同余的算法来计算的,是目前使用的比较多的一种方法。文献综述

同余与线性同余法

有整数;为模并,若b-a为M的倍数,则有a,b同时除以M后所得余数相同。则称为a与b关于模M同余,记为。

同余具有以下性质:

① 对称性:若,则。

② 传递性:若,,则。

③ 若,则,。

④ 若,则,其中(M,C)表示M和C的最大公因子。

LCG方法的一般递推公式为

其中M为模数,a为乘数,c为增量,且Xn,M,a,c均为正整数(包括0)。       

显然由(1。1)式所得的满足:,从而,应用递推公式时式中参数a,c,X0,M的选取是均匀随机数产生的关键。

例3。5 取,利用(1。1)式得到数列为:6,9,0,7,6,9,0,7,。。。

易见,且从n=5开始到n=8,我们将得到与n=1到n=4完全相同的(及),顺序也完全相同,T=4称为数列的周期。

运用同余法产生的数列中重复数之间最短的循环长度称为该初值下LCG的周期,记为T,如果满足T=M,称为满周期。

例3。6   取,利用(1。1)式得到的数列为:21,41,13,1,5,25,61,49,53,9,45,33,37,57,29,17,21,。。。,数列的周期T=16<M。

例如   取,利用(1。1)式得到数列为:6,1,8,11,10,5,12,15,14,9,0,3,2,13,4,7,6,1,。。。,数列的周期Y=16=M,故称由以上参数决定的LCG具有满周期。

易知,只有适当选取参数及M,才能得到周期长并且均匀性,随机性好的数列。

混合同余法(混合式LCG)来.自^优+尔-论,文:网www.youerw.com +QQ752018766-

当(1。1)式中满足条件参数c>0,那么该LCG方法也被称为混合同余法,或者称为混合式LCG。如例3。6就是混合同余式发生器,但参数选取的不好,使得所产生数列的周期T<M,且随机性差,以下讨论如何选取,使得所得混合发生器为满周期。

    满周期混合式LCG中的选取准则

    定理1。1  如果下列三个条件都满足,由(1。1)式定义的LCG可达到满周期

      ① c与M互素(即可以同时整除c和M的正整数只有1);

      ② 对M的任一个素因子P,(即a-1应被P整除);

      ③ 如果4是M的因子,则。

定理(1。1)给出了混合式LCG取到满周期时应满足的条件。经常取,其中L是计算机中存放一个整数值的二进制位数(称为整数的尾数字长)。这种取法有两个优点:第一是可以通过适当选取参数,使周期变大甚至达到满周期;二是可以精简计算[6]。

上一篇:基于相似信息优先的船舶建造费用测算模型
下一篇:WnMo(n=1-6)小团簇的第一性原理研究

浅谈中学数学函数最值问题的求解方法

基于决策树算法的篮球联赛预测

数形结合在中学数学中的...

浙江省工业企业发展的因子分析

中美小学数学课堂教学的比较

杭州历年中考三角形的题型分析

论数形结合在中学数学教育中的应用

张洁小说《无字》中的女性意识

新課改下小學语文洧效阅...

安康汉江网讯

麦秸秆还田和沼液灌溉对...

我国风险投资的发展现状问题及对策分析

互联网教育”变革路径研究进展【7972字】

老年2型糖尿病患者运动疗...

网络语言“XX体”研究

LiMn1-xFexPO4正极材料合成及充放电性能研究

ASP.net+sqlserver企业设备管理系统设计与开发