本文永久链接为http://johnhany.net/2013/11/random-algorithm-and-performance/ 转载请注明出处
什么叫伪随机数
在一些问题中，比如计算机仿真和模拟、密码学等应用中，需要产生一个随机数数列来解决问题。
随机数数列分为真随机数数列和伪随机数数列。真随机数数列是完全不可预测的，可以通过放射性衰变、电子设备的热噪音、宇宙射线的触发时间等物理过程得到，但无法通过单纯的软件方式获得；伪随机数数列是可预测的，严格意义上不具有随机性质，通常用数学公式的方法获得。
由于很多应用当中对“随机”数列的要求并不十分严格，而且伪随机数的产生较真随机数更为廉价、高效，所以在大多数情况下只要产生统计分布较好的伪随机数数列就能够满足应用要求。早期的伪随机数生成算法以平方取中法为主，现在则以线性同余法为主要方式。下面我会就两种方式分别给出实例，并以数据统计和图形化的方式对伪随机数生成算法的性能进行检验。
种子
正如数列需要有首项，产生伪随机数需要一个初值用来计算整个序列，这个初值被称为“种子”。种子可以是一个固定的值，也可以是根据当前系统状态确定的值。C语言用来产生伪随机数的库函数rand()的种子是固定的值，因此每次调用该函数产生的随机数数列都是相同的。所以为了获得随机性更好的数列，种子应为一个变量，该变量可以与当前系统时间、用户对键盘或鼠标操作情况有关。这里我将根据系统时间获得种子。
代码如下：
#include
unsigned long ssecond,nowtime;
unsigned long seed;
long gettime() //获得当前时间
{
time_t t;
time(&t);
struct tm *local;
local=localtime(&t);
local->tm_mon++;
ssecond=(long)local->tm_sec*100+local->tm_sec+36923;
nowtime=local->tm_sec + local->tm_min*100 + local->tm_hour*10000 + local->tm_mday*1000000 + local->tm_mon*100000000;
return nowtime;
}
在调用伪随机数生成函数之前通过seed=gettime();语句就完成了种子的初始化。
平方取中法
平方取中法是由冯·诺依曼在1946年提出的，其基本思想为：将数列中的第a(i)项（假设其有m位）平方，取得到的2m位数（若不足2m位，在最高位前补0）中间部分的m位数字，作为a(i)的下一项a(i+1)，由此产生一个伪随机数数列。即：
x(i+1)=(10^(-m/2)*x(i)*x(i))mod(10^m)