【转】线同余数产生随机数算法

线形同余产生随机数
一.线形同余算法介绍：
在计算机上产生随机数，比较普遍的一种方法是用数学递推公式产生，这样产生的序列与真正的随机数序列不同，所以称为伪随机数或伪随机序列。只要方法和参数选择合适，所产生的伪随机数就能满足均匀性和独立性，与真正的随机数具有相近的性质。计算机产生的随机数一般都只是一个周期很长的数列，不是真的随机数。也就是说，随机数一般是伪随机数，每个随机数都是由随机种子开始的一个已定的数列。
当今所流行的随机数生成程序方法之一为线形同余法。这种方法通过设置
Xn+1 = （ aXn + c ） mod   m ，n >= 0
式中的四个整数
m ， 模数        0 < m
a ， 乘数        0 <= a<m
c ， 增量        0 <=c<m
X0，开始值    0<=X0<m
而得到所求的随机数序列<Xn>。这个序列称作线形同余序列。
同余序列总是进入一个循环，这是一个事实，它最终必定在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的条件如下：
当且仅当（1）c与m互素。
（2）对于整除m的每个素数p，b=a-1是p的倍数。
（3）如果m是4的倍数，则b也是4的倍数。
就像开始提到的，伪随机数的产生都是由一个起始种子数开始的，上面描述的就是由一个种子数下能够产生的随机数的序列。这个序列的周期性是必然的，当这个周期能够满足预期的效果的时候，就是我们看到的满意的随机效果。
在确定初始种子数的时候，可以有多种形式，例如将某时刻的时钟数据做种子，通过时间的不停变化，进行随机数的求取来达到随机效果。这些都是方法问题了，不在算法讨论范畴。
二.学习建议及计划：    
根据观察和学习线形同余产生随机序列的体会，编写一个能够产生使自己满意的随机效果的汇编程序。

另外几个有用的参考：

zt随机数的算法分析

zt 随机数算法