随机数

原地址：http://hi.baidu.com/_kouu/blog/item/7a2a4a83241e0699f603a60c.html

在使用计算机的过程中，有很多情况会接触到随机数。比如，播放器的随机播放、游戏中的随机事件、等等。尽管这些东西都号称随机，但是用户体验总是会出些问 题。比如，选择了随机播放，放来放去却总是那几首歌。又比如，游戏中的随机事件，总能被有经验的玩家猜中七八成。这是怎么回事呢？

这个问题可能牵扯到的范围实在太大了：程序是否实现了随机？人的经验产生了多大作用？……甚至于，宇宙中是否存在随机？（如果宇宙中的一切都是由物质构成 的，并且物质的运动遵循固定的规律，那么宇宙中一切事物的发展轨迹就已经注定了。这就是所谓的“宿命论”。）

就我目前的理解而言，只能用“伪随机”来解释这个问题：计算机产生的随机数并不是真正的随机数。

在计算机中，经典的随机数产生算法是给定一个函数y=f(x)，每个随机数都是通过它进行一次迭代而产生的。函数f(x)的迭代过程如下：
x0, x1=f(x0), x2=f(x1), ..., xn=f(xn-1), ...
第0个随机数x0被称为种子。

在标准C中，提供函数srand()用于设置种子、rand()用于进行一次迭代，产生一个随机数。

很显然，在种子确定、迭代函数确定的情况下，迭代序列中的每一个xn都是确定的。这种算法完全不存在随机性。但是，这样的算法为什么能够用于生成随机数 呢？

通过某个函数式进行迭代，当迭代次数充分大时，迭代序列可能有几种结果：
1、收敛；
2、出现周期性重复；
3、没有规律、杂乱无章，称之为混沌；

而随机数算法所需要的就是“混沌”这个结果，为此，迭代函数是精心选择的。这时候，迭代序列中的每一个xn杂乱无章地分布在某一区间中。在没有人知道迭代 函数的情况下，姑且可以认为迭代序列是随机的。

可见，随机函数生成的随机数与真正的随机还是有很大差别的。

在C中，每次执行程序时，rand()都会生成相同的随机数序列。所以，一定要通过srand()来设置不同的种子。
有人认为，尽管随机数生成算法是“伪随机”的，但是我们可以给它设置一个随机的种子，使它产生的随机数真正随机。
但是这显然是不对的，种子和迭代函数都已经确定了，今后将要产生的数数也都已经注定了。这样的数据能称得上随机吗？
所以，通过一些客观因素（比如时间）来设置种子，可以提升随机数生成函数的表现，但是并不能改变它“伪随机”的本质。

那么，计算机能不能产生真正的随机数呢？其实，linux上有个叫/dev/random的文件，就能做到真正的随机。

/dev/random是linux内核创建的一个设备文件，每次读取这个文件，内核会输出一个随机串。
这个随机串从哪里来呢？其来源主要是外设中断。有这样一些外部设备，它们产生的中断是随机的。比如网卡，它接收到数据而产生中断的时刻基本上就是随机的。 哪怕你刻意在某一时刻向网卡发送一个报文，网卡产生中断的时刻也是很不确定的。因为报文在传输过程中将受到传输介质的影响、网卡可能先收到了别人发送的报 文、网卡收到报文后也不确定要等待多少时间CPU才进入中断（中断是不能中断正在执行的指令的）。所以，除非是刻意制造的实验环境，否则可以认为这一类外 设能够提供随机的数据。

这些随机数据被称为“熵”，内核它们存储在“熵”池中。它在每次有新数据进入时，内核还需要做一些处理，取出数据中真正随机的那一部分（比如以网卡中断的 时间为随机数据，那么“年月日”等信息显然不是随机的），然后进行一些数学变换，以便保存和输出。

实际使用中可能出现“熵”供小于求的情况，那么读/dev/random时，熵池为空，进程就要被阻塞，以等待下一个熵。于是内核又提供了另外一个文件 /dev/urandom，作为折衷，如果熵池已经读空了，则产生伪随机数。

但是，从目前常用的这些软件来看，使用真随机的估计并不多。