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

well

大家都讲讲自己知道的方法吧，这是个很实用的东东

soloforce

这个论题简直可以做一篇硕博论文了。
我们通常在高级语言中运用的随机算法函数几乎只产生伪随机数数列，而真正的随机数数列貌似很难通过某种算法生成──只要是算法生成的，它就不是随机的。所以这个论题不妨改成伪随机数生成方法，真随机数的问题还是留给高深的数学家和物理学家考虑吧：）

woolzey

我看不止是博士论文。现在连啥是随机数，怎么定义随机性这些基础问题都没搞清楚呢。姚期智就因为研究这个拿了图灵奖。

晨想

用火山爆发来作源，比较真实。嘿嘿。。。

（随机数是很难。。很难。。得到的。。）

well

我的本意如lolita所说主要是讨论伪随机。当然有兄弟能搞出真随机也不错 ：）
phrack上有篇文章就是讲依靠mouse移动来产生随机数，而mouse的移动可以看成是随机的

soloforce

第 29卷 　 第 1 5期      计算机工程 2003年 9月
在计算机上产生真随机数的探讨
         梁金千，张  跃
(清华大学自动化系，北京 100084)


    在计算机系统中，存在着大量的随机事件，常见的随机事件有：
   1) 用户的击键次数、发出的各种鼠标命令次数等。
   2) 计算机硬盘上空余的扇区数以及读取某扇区所用的时间或延迟等。
   3) 计 算 机 中 各 种 可 变 数 据 表 的 大 小, 如FAT 表 、 内 存 分 配 表等。
   4) 到目前为止，用户或计算机访问某些设备的次数等。
   5) 网络所发出或收到的数据包的多少，以及接收到的网络请求事件的多少等。
   6) 某个进程(线程)已执行的时间和系统目前正在运行的进程(线程)数等。
   7) CPU负载的变化率和由于电压波动等引起的各种硬件响应时间的变化等。
   8) CPU处理的各种硬件中断的次数和时间等。


────────────────────
不过，作者的这些论断没有什么数学证明，想当然耳。

soloforce

目前常见的伪随机数产生方法有许多种,如线性同余法、多重递归法、裴波纳契法、 位移寄存法、 反转同余法和复合线性同余法等。 其中最常见的是线性同余法中的加同余和乘同余法。

dunerunner

微秒　　　　

seamonkey

嘿嘿，我是不懂的，不过以前在NewsForge上看过一篇文章，随手加入了书签：

http://programming.newsforge.com ... 1540242&tid=140

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）。

密码学意义上的随机数目前没有一般的定论，实践中使用的方法也是五花八门。两个标准ANSI X9.17和FIPS 186中分别基于DES和SHA-1构造了一个推荐使用的算法，可以参考使用。

Post by Lolita
目前常见的伪随机数产生方法有许多种,如线性同余法、多重递归法、裴波纳契法、 位移寄存法、 反转同余法和复合线性同余法等。 其中最常见的是线性同余法中的加同余和乘同余法。