生成伪随机数的算法�C线性同余法 - 不知道要什么,便什么都想要,最后什么都要不到 - 博客频道 - CSDN.NET
同余的概念是这样描述的：
设m是一个给定的正整数，如果两个整数a，b用m除，所得的余数相同，则称a，b对模m同余。
所谓线性同余法（又叫混合同余法），就是这样的一个公式：X[i+1]=(A*X[i]+C) mod M；
经前人研究表明，在M=2^q的条件下，参数A，C，X[0]按如下选取，周期较大，概率统计特性好:
A=2^b+1=2^(log2(M)/2)+1=2^log2(sqrt(M))+1=sqrt(M)+1；b取q/2 附近的数
C=(1/2+sqrt(3))*M
X[0]为任意非负数
M ， 模数 0 < M
A， 乘数 0 <= A<M
C， 增量 0 <=C<M
Xi，开始值 0<=Xi<M
它的一个致命的弱点，那就是随机数的生成在某一周期内成线性增长的趋势，显然，在大多数场合，这种极富"规律"型的随机数是不应当使用的。
同余序列总是进入一个循环，这是一个事实，它最终必定在N个数之间无休止的重复循环。
使用该方法产生的伪随机数能不能近似真正的随机效果，跟四个整数的设置相关：
1. 序列的开始值，一般取正整数。
2. m：一个同余序列的周期不可能多于m个元素，所以，为了达到预期的随机效果，一般我们希望这个值稍稍大一点。在大多数情况下，当m = 2e（e表示计算机的字大小）时，在计算机中得到的随机效果就比较令人满意了。而且这样对于随机数生成速度也是比较合理的。
3. a：当a=1的时候，Xn=（X0+nc）mod m ，它不具有随机序列的特性；而当a=0的时候甚至更糟糕。因此，为实用起见，选择2 <= a<m比较合理。
4. c：当c=0时，数的生成过程比c！=0的时候要稍微快些，它的限制缩短了这个序列的周期长度，但是也仍然有可能得到一个相当长的周期。当c=0时被称为乘同余法，c！=0称为混合同余法。为了一般性，我建议选择采用混合同余法。
由m，a，c和X0所定义的线形同余序列得到最大的周期长度m的条件如下：
Read full article from 生成伪随机数的算法�C线性同余法 - 不知道要什么,便什么都想要,最后什么都要不到 - 博客频道 - CSDN.NET
No comments:
Post a Comment