随机数算法都是假的，Deadline才是第一生产力

Park S和Miller K所著的 Random Number Generators: Good Ones are Hard to Find 中提出了评价随机数发生器的三个准则：

• 这个函数应该是一个完整周期的产生函数。也就是说，这个函数应该在重复之前产生出0到m之间的所有数；
• 产生的序列应该看起来是随机的；
• 这个函数应该用32bit算术高效实现。

常用的随机数算法基本能够满足上述的条件（第2-4种方法在本机测试环境下可以在1.7秒内完成65535组求解且均具有较好的随机性）。我们选择了最为常用的线性同余和梅森旋转算法，以及C++11标准库提供的非确定性随机数生成设备random_device进行探究。

测试

1 随机数表法

随机数表也称乱数表，是由随机生成的从0到9十个数字所组成的数表，每个数字在表中出现的次数是大致相同的，它们出现在表上的顺序是随机的。表格形式多种，用法也很多，使用时可根据研究对象总体所含的个体数来确定使用几位随机数字，也就是可以根据需要把它当成任何数字来使用。

随机数表法的本质是用随机数字表代替签号或签筒的一种随机取样的方法。其优点是简单可行，抽样前只需对研究对象进行顺序编号；以及能保证符合抽样的“随机化原则”，抽中与否全都是偶然的，使抽取的样本更具代表性。而缺点也显而易见：由于大量的人工，在计算机等平台上难以实现。

由于随机数表法对人工要求太大，我们没有进行大量的生成与散点图分布情况验证。

2 线性同余算法

线性同余算法是目前应用最为广泛的伪随机数生成算法之一。如果对乘数和模数进行适当的选择，可以满足上述评价随机数发生器的三准则。

在C++中，线性同余的调用代码最为简单。我们利用如下代码进行了两次测试：

#define XMAX
#define YMAX
#define TIME
#include <cstdlib>
#include <iostream>
#include <ctime>
using namespace std;

int main(void) {
    int seed = (int)time(0);
    srand(seed);
    for(register int _cnt = 0; _cnt < TIME; ++_cnt) {
        cout << (int)(rand() % XMAX) << "," << (int)(rand() % YMAX) << endl;
    }
    return 0;
}

每行输出两个数字，分别是对应散点图中每个点的横纵坐标。XMAX和YMAX分别控制横坐标和纵坐标的最大值，TIME对应输出行数（即点的个数）。得到的结果如下：
原始测试数据

第一次测试时间2018-8-23 19:44:07，在500*500的区域内生成了250组数据，得到了下面的散点图：

第二次测试时间2018-8-23 19:55:08，在1000*1000的区域内生成了5000组数据，得到了下面的散点图：

初步测试的结果显示出了比较好的随机性。但考虑到线性同余发生器的周期一般在1 000 000至10 000 000之间，生成的伪随机数质量是不如下文所述的梅森旋转的。

3 梅森旋转算法

梅森旋转算法由松本真和西村拓士在1997年开发，基于有限二进制字段上的矩阵线性递归，可以快速产生高质量的伪随机数。梅森旋转算法同样是目前应用最为广泛的随机数生成算法之一，并且终将淘汰线性同余算法（虽然目前是并存之势）。它是R、Python、Ruby、IDL、Free Pascal、PHP、Maple、Matlab、GMP和GSL等工具/语言的默认伪随机数产生器，C++ STL在万众瞩目的C++11标准中也终于支持该算法。算法实现的过程中，参数的选取取决于梅森素数，故得名。

其优点首先就是周期非常长，最常用的MT19937的周期达到4 294 967 295（2的32次方减1）。尽管如此长的周期并不必然意味着高质量的伪随机数，但短周期确实会带来许多问题。其次是速度快，在当时是所有伪随机数发生器中最快的（当然，有些在统计学意义上的不正确的随机数生成器确实比梅森旋转快）。

在C++11中，梅森旋转的STL调用如下：

#define XMAX
#define YMAX
#define TIME
#include <iostream>
#include <ctime>
#include <random>
using namespace std;

int main(void) {
    time_t now = time(0);
    char* dt = ctime(&now);
    unsigned seed = (int)now;
    mt19937 rd(seed);
    for(register int _cnt = 0; _cnt < TIME; ++_cnt) {
        cout << (int)(rd() % XMAX) << "," << (int)(rd() % YMAX) << endl;
    }
    return 0;
}

其中XMAX YMAX TIME和上文作用相同。下同。
测试结果如下：
原始测试数据

第一次测试时间2018-8-23 20:04:46，在300*300的区域内生成了250组数据，得到了下面的散点图：

第二次测试时间2018-8-23 20:54:34，在2000*2000的区域内生成了8000组数据，得到了下面的散点图：

测试结果也显示出梅森旋转较好的随机性。

4 /dev/urandom随机二进制流

/dev/random和/dev/urandom是Linux系统中提供的随机伪设备（不是伪随机设备!），提供永不为空的随机字节数据流。它们利用当前系统的熵池来计算出固定一定数量的随机比特，然后将这些比特作为字节流返回。也就是说，用/dev/random和/dev/urandom生成的随机数在一定情况下可以视为真随机数。

两者的区别在于，/dev/random依赖系统中断，当中断不足时/dev/random会封锁，直到有新的足够多的可用中断，才会继续生成，而/dev/urandom则不会阻断程序。因此，/dev/random的随机性更好，而/dev/urandom则会带来更流畅的数据流。

Linux中C++11的random_device利用的是/dev/urandom设备。我们通过如下代码进行测试：

#define XMAX
#define YMAX
#define TIME
#include <iostream>
#include <ctime>
#include <random>
using namespace std;

int main(void) {
    random_device rd;
    for(register int _cnt = 0; _cnt < TIME; ++_cnt) {
        cout << (int)(rd() % XMAX) << "," << (int)(rd() % YMAX) << endl;
    }
    return 0;
}

测试结果如下：
原始测试数据

由于不需要时间作为seed，故没有输出时间。

第一次测试在300*300的区域内生成了250组数据，得到了下面的散点图：

第二次测试在2000*2000的区域内生成了8000组数据，得到了下面的散点图：

但是！
/dev/random有一个得天独厚的优势：虽然随机性依然不可能达到完美，也会中断无法读取，但区别于其他的固定算法，从这里出来的随机字节绝对不可能被还原发生过程！因为是从系统熵池中直接读取，当你再次用同样的方式调用同样的函数，也无法完全还原上一次系统的状况，包括但不限于系统进程状态、噪声、中断。
因此，/dev/random多被用于对安全性有一定要求的场合，比如RSA私钥的产生。

结论

其实也没有什么结论好说，毕竟“随机数”这么个话题大家已经讨论了几十年了。

从探究结果不难看出，线性同余算法最大的好处便是实现简单，而长周期高质量高速度的梅森旋转算法能够在大多数情况下生成（在一定条件下的）最佳结果。如果可能的话，调用/dev/random或者/dev/urandom将会对随机数的质量和安全性带来极大的提升。

鉴于个人抱有“Windows是这个世界上最差劲的系统之一”的观点，我十分感激C++11为Linux带来的random_device并且认为该方法是目前而言计算机生成随机数的最佳方法。

随机数发生浅谈作者为叶奕，本文所有内容（包括但不限于文本、图片、代码）采用知识共享 署名-非商业性使用-禁止演绎 4.0 国际许可协议（CC BY-NC-ND 4.0）进行许可。
您可以自由地转载或分享本文，但不得用于商业用途和/或更改文章内容，并保留原作者署名。