随机数生成算法 - [技术&趋势]
版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://buerpool.blogbus.com/logs/10182011.html
这两天没事，就写了写数学课上老师说的那个“蒲丰投针实验"的程序。接触到了一
些随机数生成方面的东西，写出来跟大家分享一下。
对于计算机生成随机数这个东西，以前有过一些浅显的认识。只知道计算机不能生
成真正的随机数，只能用一定的方法来模拟随机数，叫做伪随机数。比如 C 语言
里面的 rand()函数，就是一个伪随机数发生器。之前也知道有个叫做 seed 的东西，
知道每次调用 rand()之前都需要重置一下 seed。以往的编程当中，一般都用系统
时间来产生 seed。但是 seed 是什么东西，为什么要用 seed，则完全不清楚是怎
么一回事了。
网上的一些文章中提到，C 语言中伪随机数生成算法实际上是采用了"线性同余法”。
具体的计算如下：
Xi = (Xi-1 * A + C ) mod M
其中 A,C,M 都是常数（一般会取质数）。当 C=0 时，叫做乘同余法。srand()函
数置的 seed 实际上会作为 X0 被代入上式中，然后每次调用 rand()函数都会用上
一次产生的随机值来生成新的随机值。这样我们可以看出实际上用 rand()函数生
成的是一个递推的序列，一切值都来源于最初的 seed。这就不难解释为什么当初
始的 seed 取一样的时候，得到的序列都相同。也就解释了为什么我们需要调用系
统时间这种变化的值来充当 seed 了。
C 语言里面有 RAND_MAX 这样一个宏，定义了 rand()所能得到的随机值的范围。
在 C 里可以看到 RAND_MAX 被定义成 0x7f，也就是 32767。据此我们可以
推测 rand()函数里递推式中 M 的值就是 32767。据说在 LInux 里面这个值被定
义的更大一些，也就是说 LInux 里生成的随机值的范围更大。
线性同余法生成的随机数的随机性并不是很好，并不是真正的满足均匀分布，仅仅
能满足一般的要求。 用这个做概率方面的模拟还是很有限的，网上搜到了一些关
于计算机模拟的文章，提到了一些很专业的方法，比如蒙特卡洛方法等等。由于没
想深入，就没往下看。
比较有意思的是在 CSDN 上搜到了 sjd163 一篇文章讲到了一种通过交换来得到
随机序列的方法。主要的依据是热力学第二定律的熵增加原理。主要的思想是将有
序的序列通过一定的交换将有序变成无序。思想类似于扑克牌的洗牌。假设扑克牌
是从小到大的顺序放好的，通过多次的洗牌之后扑克牌的顺序性就逐渐消失，变的
随机。换句话说，系统的熵值变大。而且这种过程是不可逆的，只能从有序变成无
序，不能从无序变成有序。
