
现代计算机中的随机数都是用算法产生的伪随机数(
)。这些算法本质上都是确定性的,给定一个输入就会有一个固定的可预测的输出,因此产生的数都不是真正意义上的随机数。
具体算法包括平方取中法、乘积取中法、加同余法、乘同余法、乘加同余法、梅森旋转法等。其中最常用的是乘加同余法(又称“线性同余法“,长期以来被视作生成伪随机数的”标准“算法),最新的是梅森旋转法(1997年提出,现已加入C++11豪华午餐)。此外,还有一些比较特(qi)别(pa)的伪随机数算法,比如Stephen Wolfram大神的
,在Mathematica中就可以用这个Rule 30来生成伪随机数。因为这些算法都是确定性的,所以伪随机数发生器的第一个输入就尤为重要,这第一个输入被称为”种子“(seed)。在相同的算法、相同的配置下,相同的种子将产生相同的随机数序列,这就是为什么你在学C/C++时老师会告诉你在程序中首次调用rand()函数之前务必要有一行srand((int)time(0));
事实上的确有可以产生真随机数的方法,主要包括随机数表法和物理法:前者是记录大量随机实验的结果并将其整理成表以备使用;后者则是将某些放射性同位素的衰变事件或者电子计算机的固有噪声作为产生随机数的物理源。这两类方法的缺点也显而易见:前者需要耗费大量人力物力进行随机实验,并且其结果需占用大量存储空间;后者则需要在计算机上添加特殊装备,更不用提放射性核素的获取管理以及很多人对“放射性”根深蒂固的恐惧。
总之经过数十年的实践,人们最终还是选择了伪随机数,因为其原理简单、耗费资源少、产生随机数的成本低;当然,为了保证伪随机数足够“随机”,人们会对其做大量校核,相关的专家学者也会不断研究更好的伪随机数产生算法。
