线同余数产生随机数算法

时间:2022-09-19 16:05:06

 

线形同余产生随机数
一.线形同余算法介绍:
在计算机上产生随机数,比较普遍的一种方法是用数学递推公式产生,这样产生的序列与真正的随机数序列不同,所以称为伪随机数或伪随机序列。只要方法和参数选择合适,所产生的伪随机数就能满足均匀性和独立性,与真正的随机数具有相近的性质。计算机产生的随机数一般都只是一个周期很长的数列,不是真的随机数。也就是说,随机数一般是伪随机数,每个随机数都是由随机种子开始的一个已定的数列。
当今所流行的随机数生成程序方法之一为线形同余法。这种方法通过设置
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的倍数。
就像开始提到的,伪随机数的产生都是由一个起始种子数开始的,上面描述的就是由一个种子数下能够产生的随机数的序列。这个序列的周期性是必然的,当这个周期能够满足预期的效果的时候,就是我们看到的满意的随机效果。
在确定初始种子数的时候,可以有多种形式,例如将某时刻的时钟数据做种子,通过时间的不停变化,进行随机数的求取来达到随机效果。这些都是方法问题了,不在算法讨论范畴。

 

 

 

 

 

 

 

http://hi.baidu.com/serial_story/blog/item/2ae42295b88ef40d7af480ba.html