[C++][标准库] 随机数的生成方式、性能对比、mingw的问题

写在前面

本篇文章包含了以下内容：

• 随机数的两种生成方式：HRNG 、PRNG
• HRNG 和 PRNG 在 C++中的执行时间的比较
• mingw 的 std::random_device 存在的问题

随机数的生成方式

参考资料：

[1] https://en.wikipedia.org/wiki/Random_number_generation

[2] 电脑取随机数是什么原理，是真正的随机数吗？ - 王納米的回答 - 知乎

随机数生成（Random Number Generation, RNG）的方式一般有两种，分别为：

• 硬件生成随机数Hardware RNG，原理是用某个仪器一直探测环境中的物理量，将该物理量作为随机数，见[2]。由于人类目前还无法对真实的物理环境进行建模，所以无从预测下一个产生的随机数是什么。因此，HRNG可以看作真随机数，[2]中给出了一个具体的例子。

  另一个例子是 Intel 和 AMD CPU指令集中的 RDRAND 指令，该指令基于clock shift生成随机数：

  One way to build a hardware random number generator is to use two independent clock crystals, one that for instance ticks 100 times per second and one that ticks 1 million times per second.

  On average the faster crystal will then tick 10,000 times for each time the slower one ticks. But since clock crystals are not precise, the exact number of ticks will vary. That variation can be used to create random bits.

  For instance, if the number of fast ticks is even, a 0 is chosen, and if the number of ticks is odd, a 1 is chosen. Thus such a 100/1000000 RNG circuit can produce 100 somewhat random bits per second. Typically such a system is biased—it might for instance produce more zeros than ones—and so hundreds of somewhat-random bits are “whitened” to produce a few unbiased bits.

• 算法生成随机数，比如c++中的 mt19937梅森旋转算法即为一种软件层面的随机数生成算法算法。如果知道了seed和算法的具体实现，别人就可以知道你生成的随机数序列。所以，又被称为 伪随机数生成器 Pseudo RNG。其他的PRNG算法包括 Xorshift，linear congruential generators等。

HRNG vs PRNG

参考资料：

[1] https://stackoverflow.com/questions/39288595/why-not-just-use-random-device

从上面的描述中可以看出，硬件生成的随机数似乎更好一些，是真随机数，而软件层面的随机数容易被人破解。但是在C++代码中，人们一般不直接使用HRNG。而是利用HRNG为PRNG生成一个种子，然后利用PRNG生成随机数，比如如下代码：

std::random_device rd; //linux下，读取/dev/random获取硬件产生的随机数
std::mt19937 e{rd()}; // or std::default_random_engine e{rd()}; 用HRNG作为PRNG的种子
std::uniform_int_distribution<int> dist{1, 5};

dist(e); // get random numbers with PRNG

为什么不直接使用 std::random_device呢？ 可以从效率和可解释性两个角度解释了这个问题，见[1]，讲的比较清楚，这里我就不过多解释了，只补充一个两者的执行速度的对比。

这里用 google-benchmark 对比了linux（ubuntu 20.04, gcc 9.2.0)下 std::random_device 和 std::mt19937 的执行速度：

• 所使用的代码如下：

  #include <benchmark/benchmark.h>
  #include <random>
  
  static void BM_PRNG(benchmark::State& state) {
      std::random_device rd;
      std::mt19937 e{rd()};
      for (auto _ : state){
          e();
      }
  }
  BENCHMARK(BM_PRNG);
  
  static void BM_HRNG(benchmark::State& state) {
      std::random_device rd;
      std::uniform_int_distribution<int> dist(0, 9);
      for (auto _ : state){
          rd();
      }
  }
  BENCHMARK(BM_HRNG);
  
  BENCHMARK_MAIN();

• 运行结果如下：

  Run on (1 X 2494.14 MHz CPU )
  CPU Caches:
    L1 Data 32 KiB (x1)
    L1 Instruction 32 KiB (x1)
    L2 Unified 4096 KiB (x1)
    L3 Unified 28160 KiB (x1)
  Load Average: 2.70, 3.15, 16.35
  -----------------------------------------------------
  Benchmark           Time             CPU   Iterations
  -----------------------------------------------------
  BM_PRNG          35.9 ns         17.8 ns     39254461 
  BM_HRNG          1310 ns          640 ns      1091579

• “真”随机数的耗时大概是“伪”随机数的 37倍，非常之慢。

这非常类似非对称加密和对称加密，非对称加密（RSA）通常不用于直接加密信息，而是用于加密并交换对称密钥，然后用对称密钥（比如AES-256）交换要传输的信息，因为对称密钥加密解密的速度更快，但是相对更不安全。

mingw 中 std::random_device的问题

分别在GCC，MSVC，Mingw中执行下述代码：

#include <random>
#include <iostream>

void test() {
    std::random_device rd;
    std::cout << rd() << ", ";
    std::cout << rd() << ", ";
    std::cout << rd() << std::endl;
}

int main() {
    test();
    test();
    test();
    return 0;
}

msvc

gcc

Mingw 8.1.0

---

显然，gcc和msvc下的random_device每次都产生了不一样的随机数序列。

然而，mingw下的random_device每次都产生了同样的序列（deterministic）。

A notable implementation where std::random_device is deterministic is old versions of MinGW (bug 338, fixed since GCC 9.2). The latest MinGW Versions can be downloaded from GCC with the MCF thread model.

From: https://en.cppreference.com/w/cpp/numeric/random/random_device

幸运的是，这个问题在mingw 9.2中被修复了。

Add support for additional sources of randomness to std::random_device,
to allow using RDSEED for Intel CPUs and rand_s for Windows. When
supported these can be selected using the tokens “rdseed” and “rand_s”.
For -w64-mingw32 targets the “default” token will now use rand_s, and
for other i?86-- and x86_64--* targets it will try to use “rdseed”
first, then “rdrand”, and finally “/dev/urandom”.

From : https://patchwork.ozlabs.org/project/gcc/patch/20190529144517.GA9078@redhat.com/

这算mingw的一个bug吗？实际上，并不算，因为C++标准过于宽松，它允许random_device每次产生同样的随机数序列：

std::random_device may be implemented in terms of an implementation-defined pseudo-random number engine if a non-deterministic source (e.g. a hardware device) is not available to the implementation. In this case each std::random_device object may generate the same number sequence.

From: https://en.cppreference.com/w/cpp/numeric/random/random_device