【技术前沿】“恋上”随机数

作者：研发部　杨盛海

　　如何使用电脑产生随机数，这个问题有时候会让人疯狂地痴迷其中，因为很少有算法能像生成随机数这样神秘而诡异。

　　根据现代计算机的结构，产生真正的随机序列几乎不可能，某位前辈大师曾曰：“如果有人相信计算机能产生随机的序列，那他一定是疯了。”谁说的不重要，重要的是这句话，记住即可，不必问为什么。

　　既然计算机本身没办法生成随机数，仍可以借助一些辅助办法来生成，举一个理想又比较形象的办法：做一个机器手臂，控制端接入电脑，给它放上一把硬币，要多少二进制位就放多少硬币，编上号，然后点击生成，电脑控制手臂一扬，撒一桌子硬币，正面为1，背面为0，用摄相头一录，把二进制数转换为十进制数，绝对的随机。

　　以上方法实际上不怎么可行，成本太高不说，速度也太慢，性价比太低。实际上有些工作人员使用盖格计数器，在盖格计数器前放一块衰变概率为50%的放射性物质，盖格计数器用来探测衰变，并将数据发送到电脑，这种方法即使有人使用，也是近乎神话一般。总之要产生真正的随机数，必然要和某种自然发生的随机事物相关联。

　　如果这些产生真正随机数的办法指望不上，那只能借助随机数公式来生成近似于随机数的伪随机数。现在的随机数公式大多利用线性同余的原理，基本公式就是：

　　Xn+1 = （ aXn + c ） mod m ，n>= 0 。
　　式中的四个整数：
　　m ， 模数 0 < m
　　a ， 乘数 0 <= a<m
　　c ， 增量 0 <=c<m
　　X0，开始值 0<=X0<m

　　而这个Xn就是我们所说的随机数序列，每一个随机数是下一个随机数的种子。这个公式中比较重要的操作就是取模的操作(mod)，取模操作实质上是把一个大数转换为一个小范围内的数，超出这个小范围之后再从头开始。从0到9范围内的数转换为对3取模的数就是0、1、2、0、1、2、0、1、2、0。任何一个大数都可以转换过来，这有点像赌博工具转轮盘。转轮盘只有那么十几个方位，用手使劲一转，不管转多少圈，最后指针指向的无非就是这十几个方位之一，这就是取模的意思。

　　公式的意思是使用上一次生成的随机数，乘上一个数再加上一个数，再对另外一个数取模，这个过程同样可以看作是转轮盘，上一次转完后，指针停在一个地方，从这个地方再加一把力，乘上一个数再加一个数，使得轮盘又多转几圈，转到哪个地方，取下模便知道。

　　这个求随机数的方法好不好，关键要看它的这几个参数，m、a、c和X0，如果这几个数选不好，很可能生成一系列有规律的数，就失去公式的意义了。比如，当a=c=0时，无论另外两个取什么数，都只能生成一串数字0，另外，当a和c取得太小，结果肯定也是不满意的，比如当a=2,c=1时，取模为10，此时设定X0为0，那么依次生成的序列为：

　　X0=0
　　X1=1
　　X2=3
　　X3=7
　　X4=5
　　X5=1
　　.
　　.
　　.

　　一开始还好，到X5时我们发现出现重样的数字1，这很致命，可以肯定的是，以后序列会重复之前的一段序列，这里是1、3、7、5，并没完没了地循环下去，这个序列简直太不像话了。所以，选择合适的参数是构造这个随机数公式的主要工作。

　　我们前面说过，这个过程像转轮盘，要想转完轮盘后，指针指向的位置更随机一些，不能仅仅轻推一下，这样显得太假。必须使足力气狠狠地抡它一下，这样，当它停下来的时候才更像是随机。体现在公式里就是基本上要把a和c设置得尽量大，一般在应用的时候要生成一个固定范围里的随机数，我们经常看得到的是32位的数，那么m也就是固定的，就是2的32次方。至于X0,也是不太重要，因为后一个数只需要前面的那个数做种子。

　　可以想象a和c也不能设置得太大，太大了，计算机算得比较累，也不合算。所以这两个数设置得合适即可，计算机经典算法中给出这样的数：a=1103515245,c=12345，并宣称这是一个很漂亮的算法。至于这两个数如何推导出来，我还没追究清楚，用到数论的知识，实在是比较复杂。

　　我们秉承着一种怀疑的态度来看这个算法，它是如此的简单，能不能经得住推敲使用？有人说了，这个公式，我知道前一个数，就能推导出后一个数，如何算得是随机数呢？他说得很对，实际上我们也没有求随机数，我们只是在求伪随机数，如果这个人不知道公式，就不知道下一个数是什么，我们的目的就达到了。

　　又有人说，那我们如何来判定这些生成的数效果好不好呢？一是用眼看，看起来合适就行，如果非要弄个研究结果，那就使用第二个办法，使用统计方法，生成0到9范围内的数10000个，那么每个数生成的次数基本上都应该在1000个左右，不能偏差太多。网上有一个统计的例子，来说明那个经典算法的效果，列位看官可以自己看：

　　数-次数
　　0 - 1015
　　1 - 1024
　　2 - 1048
　　3 - 996
　　4 - 988
　　5 - 1001
　　6 - 996
　　7 - 1006
　　8 - 965
　　9 - 961

　　还可以吧？如此简单的公式能得出如此逼真的随机数，很多数学工作者都有些不服气，他们想在这个基础上再进一步研究更加随机一些的算法，很多人适得其反，弄出来的数反而不好。从这个角度上也可以看出，一些事情不是弄得越复杂越好，回过头来把事往简单的方向思考一下，往往会得到意想不到的效果。从这个随机数公式来看，正是印证这一句至理名言：美丽的极至是简约。我们在设计算法的时候应当时刻牢记这一点，设计出简单却非常有内涵的算法。