最新消息:20210816 当前crifan.com域名已被污染,为防止失联,请关注(页面右下角的)公众号

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

工作和技术 crifan 2129浏览 0评论

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

线形同余产生随机数
一.线形同余算法介绍:
在计算机上产生随机数,比较普遍的一种方法是用数学递推公式产生,这样产生的序列与真正的随机数序列不同,所以称为伪随机数或伪随机序列。只要方法和参数选择合适,所产生的伪随机数就能满足均匀性和独立性,与真正的随机数具有相近的性质。计算机产生的随机数一般都只是一个周期很长的数列,不是真的随机数。也就是说,随机数一般是伪随机数,每个随机数都是由随机种子开始的一个已定的数列。
当今所流行的随机数生成程序方法之一为线形同余法。这种方法通过设置
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 随机数算法

转载请注明:在路上 » 【转】线同余数产生随机数算法

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
79 queries in 0.177 seconds, using 22.13MB memory