资源描述：
《无周期伪随机数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、无周期伪随机数生成方法—素数的应用郭凤鸣(中国地质大学.武汉，430074)摘要混合同余法生成的伪随机数序列最大周期为M，改进的混合同余法生成的伪随机数序列最大周期扩大到(M-1)M。无周期伪随机数生成方法解决了伪随机数生成的周期问题。关键词随机数，混合同余法，改进的混合同余法，素数分类号:O29AGeneratingmethodofcycle-freepseudorandomnumbers－applicationofprimenumberGuoFengming(ChinaUniversityofGeosc
2、iences,Wuhan430074)AbstractThemaximumcycleofpseudorandomnumbersequencegeneratedbymixedcongruencemethodisM，Themaximumcycleofpseudorandomnumbersequencegeneratedbyimprovedmixedcongruencemethodis(M-1)M，thegeneratingmethodofcycle-freepseudorandomnumbersresolves
3、thecycleproblemofpseudorandomnumbergenerator。Keywordsrandomnumbers,Mixedcongruencemethod,Improvedmixedcongruencemethod,Primenumbers.一引言Lehmer于1951年提出的混合同余法，具有速度快、内存省、周期长、统计特性好等优点。在各个领域得到广泛应用，几乎所有的计算机语言生成随机数的库函数都选用这一方法。过去的几十里，对于混合同余法计算公式xi+1=(axi+b)modM(1)r
4、i+1=xi+1/M（2）人们进行了很多研究，旨在寻找较好的参数x0、a、b和M，以生成较长周期的均匀伪随机数序列。到目前为止，由Hull和Dobell给出的证明是最好的。当且仅当x0、a、b和M满足下列条件时，可以得到周期为模数M的伪随机数序列。1.b和M互质；2.设q为某一质数，取M分别能被q和4整除。总之，对于给定的M，无论如何改变x0、a、b的值，生成的伪随机数序列最大周期不会超过模数M。在实际应用中，为了得到数量较多的伪随机数不得不选用较大的M。例如在字长为32位的计算机系统中取M为-1。我们有个
5、想法：以前的研究，在生成伪随机数序列时，x0、a、b和M都是基于固定不变的常数。假若把x0、a、b和M看作参变量，在伪随机数生成过程中，让它们可以变化，能否生成较好的伪随机数序列呢？按照这一想法，对x0、a、b和M的不同取值进行了大量计算、比较和统计分析，1992年我们提出了改进的混合同余法。其基本思想是：对于(1)式取M为素数，b为变量，b=i=1,2,3,…，经过适当选择a，使得生成伪随机数序列的周期可以达到(M-1)M。下面给出一个实例，取M=7，a=3，x0=5，b=1,2,3,…,50，计算50个
6、伪随机数如表一。6表一50个伪随机数表52161126535563202230646604313341050015424452161126从表一中可以看出，其中前42个数无周期性，第43个数之后，开始周期重复。用这一方法得到的伪随机数，经检验满足均匀性和独立性要求。新的计算数据，引进素数作为增量b,又有了新的进展，使得生成无周期伪随机数成为可能，介绍于此。二无周期伪随机数生成方法1—用素数作为增量将(1)式中b的取值变为b=x1，x2，x3……=2,3,5,7,11,13……，其中xi为素数。这时生成的伪随
7、机数序列周期会更长。表二是取M=7，a=3，x0=3，b=3,5,7,11,13,17,19,……时，计算得到的350个伪随机数。表中伪随机数的数量350已经大于M，没有看到重复周期。我们计算到3000>M>>M个数据，也没有看到重复周期，以此推测周期达到无限大。进一步计算证明这种推测是正确的。表二350个伪随机数表(M=7,a=3)3564254345025242304602463563652425360256121016503024310356141354340106053462302314256340
8、6565463123020415606231234142540165612024561401254123156545030212056530602012356012315606563025242360230156161505630326214150123041521215012302352316214562345635652425404124203162065623531210241063023412353141
