从一个具体的例子说起：如何均匀生成 1 亿以内的随机数？ 所谓“均匀”，意味着生成概率相等。

从 rand() 函数开始

生成随机数，第一反应是使用 rand() 函数^[1]。rand()
函数是 C 语言中用来生成随机数的函数：

#include <stdlib.h>

void srand(unsigned int seed);
int rand(void);
int rand_r(unsigned int *seedp);

rand()
函数可以随机生成 [0, RAND_MAX]
之间的数字。RAND_MAX 一般是 2147483647^[2]。

传统的 rand()
函数使用前需要使用 srand()
函数设置随机种子。由于 rand()
函数内部使用了静态变量保存状态，调用 rand() 函数时会进行加锁^[3]，并且是不可重入的。rand_r()
是 rand()
的可重入版本，其使用参数 seedp
来保存相应的状态。

为了生成 1 亿以内的随机数，最简单的方式是取模：rand() % 100000000
。

但是很可惜，这样子做是不对的。因为这样做对于 [0, 99999999]
这 1 亿个数字来说，概率是不相等的^[4]。比如，随机生成数字 0 的情况有 22 种可能；但是随机生成数字 99999999 的情况只有 21 种。

C++ 的 uniform_int_distribution

从 C++11 开始，标准库提供了 std::uniform_int_distribution^[5] 用于均匀地生成某个范围内的随机整数。（也提供了 std::uniform_real_distribution^[6] 用于生成某个范围内的随机浮点数。）

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int32_t> distrib(0, 99999999);
    for (uint32_t i = 0; i < 10; i++)
    {
        std::cout << distrib(gen) << std::endl;
    }
}

关于 std::random_device 和 std::mt19937

std::mt19937^[7] 是 C++ 标准库提供的基于梅森旋转（Mersenne Twister）算法的伪随机数生成器，可以快速产生高质量的伪随机数，修正了古典随机数发生算法的很多缺陷。std::mt19937
生成的是 uint32_t
的随机数，它还有另外一个孪生版本 std::mt19937_64
用于生成 uint64_t
的随机数。

std::random_device^[8] 是 C++ 标准库提供的 "真"随机数生成器，具体实现与平台有关。在 Linux 上，比较简单的实现是可以从 /dev/random
读取。一般情况下，std::random_device
每次生成随机数都需要消耗“熵池”中的熵，速度较慢，且当墒池中的墒耗尽时可能发生阻塞，所以不适合用于快速生成伪随机数序列，而适合用于作为伪随机数生成器的种子。

除了 std::mt19937
/ std::mt19937_64
，C++ 标准库还提供了：

• 基于线性同余（Linear Congruential）的伪随机数生成器 std::minstd_rand^[9]。通过线性同余方法构建的伪随机数生成器比较“脆弱”，其内部状态可以轻易地由其输出演算得知。
• 基于带进位减法（Subtract-With-Carry）的伪随机数生成器 std::ranlux24_base 和 std::ranlux48_base^[10] ，分别生成 uint32_t
  和 uint64_t
  的随机数。带进位减法是一种时滞斐波那契伪随机数生成器，用于改进标准的线性同余生成器。

随机数生成器的 benchmark

总的来说，无论是性能还是随机数的质量，std::mt19937
/ std::mt19937_64
都是其中出类拔萃的伪随机数生成器。

小结

1. 虽然 rand()
   取模的方式造成的随机数不均匀概率不算特别大，但具体影响因应用而异，建议尽量避免使用这种方式。
2. 使用 rand()
   的时候，比较方便的是使用 time(nullptr)
   作为随机种子，但是会有一些问题：
1. 一方面 time(nullptr)
   一秒钟才变化一次，作为随机种子变化频率太低。
2. 另一方面 time(nullptr)
   不够随机，很容易被预测。
3. rand()
   内部会加锁，可以使用 rand_r()
   避免；但是总体来说，写 C++ 代码，建议不要使用 rand()
   系列的函数。
4. std::random_device
   生成随机种子；std::mt19937
   / std::mt19937_64
   生成随机数；std::uniform_int_distribution
   生成某个范围的随机数。我认为是一个方便又安全的随机数生成组合。

参考资料