[算法]请大家讨论一下随机数的生成方法

well

真随机数的产生可以通过安装一台物理随机数发生器,把具有随机性质的物理过程变换为随机数.但缺点是不能产生与原来完全相同的随机数,对计算结果不能进行重复检查.

伪随机数介绍一下应用比较广的一个方法:素数模乘同余法.
具体原理不作介绍,感兴趣的朋友可以参考相关资料(统计计算).
    x[n] = 3125x[n-1] (mod 2^35 - 31)
    r[n] = x[n]/(2^35 - 31)
    x[0]为<M的任意正整数
    n=1,2,3...     [n]表示下标n

对递推公式为 x[n]=ax[n-1](mod 2^L-g),可以用如下方法使用溢出原理处理除法
令z[n]=ax[n-1](mod 2^L),记k=ax[n-1]/2^L,则
x[n]=z[n]+kg     当z[n]+kg<2^L-g
x[n]=z[n]+kg-(2^L-g),当z[n]+kg>=2^L-g

对于字长大于等于32的计算机,有如下程序.程序用道了溢出原理处理除法
[php]
FUNCTION RAND(IX)
INTEGER*4 IA,I15,I16,K,M
INTEGER*4 IX,IX0,IX1,IX2,IXX
DATA IA,I15,I16/16807,32768,65536/
DATA M/2147483647/
#以下计算k=ax[n-1]/2^31
IX0 = IX/I16
IX1 = (IX-IX0*I16)*IA
IX2 = IX1/I16
IXX = IX0*IA+IX2
K = IXX/I15
#以下用溢出原理计算z[n]
IX = IX*IA
IF (IX.LT.0) IX = IX+M+1
M0 = M-K
IF (IX.LT.M0) THEN
    IX = IX+K
ELSE
    IX = IX-M0
ENDIF
RAND = IX*4.656612875E-10
RETURN
END
[/PHP]

well

Post by woolzey
如果质量要求的高，我个人观点，目前比较好的算法是MT19973（M. Matsumoto and T. Nishimura, Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions on Modeling and Computer Simulation, 8(1):3--30, 1998）。

能否将这篇文章贴出来或者发到我的邮箱: linuwa [at] gmail.com   我这里不能上外网,谢谢!

chinarrr

以前一直好奇老虎机是如何做随机的，还想自己去算一下赢几个铜板，若干年后才知道计算机做随机是多么复杂的事情

zhenghj1024

记得manual里有讨论，不过忘记man什么看到的了



“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”-John von Neumann (1903-1957)

Iambitious

linux内核中有提供（理论上完全随机）产生随机数的函数。

Charlesjun

线性同余法产生伪随机数，正在做作业！

zxd123314

用相对时间做随机数（毫秒级），一般人无法操控！

linux的随机数只是在用设备消息而已。

keyone

伪随机和真随机
http://linuxtoy.org/archives/pseudo-random-vs-true-random.html