乘同余发生器的概率分布与快速算法

Probability Distribution and Rapid Algorithms of Multiplicative Linear Congruential Generator

证明了乘同余发生器周期的充要条件 ,从而得知素数模发生器要取最大周期的唯一途径是乘数为模的一个原根。证明了乘同余发生器全周期序列中相继两项的大小分布规律 ,该结果说明在一个周期内 ,后继项比前项小的概率等于 1 /2。最后针对乘同余发生器的特点 ,设计了乘同余发生器的快速算法 ,并给出了 C+ + 实现源程序。

The sufficient and necessary condition can get a period of multiplicative generator. Thus the only method is that the multiplicativer is a primitive root of the module to get the maximum period for a prime module multiplicative generator. The probability distribution for adjacent items relation is proved. In a period of a prime module multiplicative generator, it is equal to 1/2 that the probability for the subsequence of any item is less than the item. For multiplicative linear congruential generator, the rapid and portable algorithm implementation is given in detail. And the C ++ source programs are given to calculate the product module.