随机数生成导论

能够生成随机数在某些程序中极具价值，尤其适用于游戏、统计建模以及需要加解密数据的密码学应用。以游戏为例——若缺乏随机事件，怪物将永远以同一方式攻击，宝藏永远相同，地牢布局永不变化……这将使游戏索然无味。

现实生活中，我们常通过抛硬币、掷骰子或洗牌来制造“随机”。这些现象并非真正随机，而是涉及大量物理变量（重力、摩擦、空气阻力、动量等），以致几乎无法预测或控制，从而对普通人而言等同于随机。

然而，计算机无法利用这些物理变量——它不能抛硬币、掷骰子或洗真牌。现代计算机运行于受控的电子世界，一切皆为二进制（0 或 1），没有中间状态。因此，计算机天生被设计为产生可预测结果：当你要求计算 2 + 2 时，你总希望答案是 4，而非偶尔得到 3 或 5。

因而，计算机（至少通过软件）通常无法生成真正随机数。现代程序改用算法来模拟随机性。

本节将深入探讨程序中随机数的生成理论，并引入后续课程将用到的术语。

算法与状态

首先，我们简要回顾“算法”与“状态”的概念。

算法是为解决某问题或生成有用结果而制定的有限指令序列。
例如，老板给你一个包含若干未排序姓名的文本文件，让你排序。由于文件小且不常做，你决定手工排序。一种可能步骤如下：

1. 创建一个空列表存放已排序结果；
2. 在未排序列表中找出按字母顺序最靠前的姓名；
3. 将该姓名从未排序列表剪下并粘贴到已排序列表末尾；
4. 重复步骤 2-3，直至未排序列表为空。

上述步骤即为一个排序算法。算法具有可复用性：若明日老板再给你一份新名单，你只需按同一算法操作即可。

由于计算机执行指令与处理数据远快于人，算法常以编程语言实现，实现自动化。在 C++ 中，算法通常封装为可重用函数。

以下示例展示了一个简单算法：生成一个序列，每个后继数字比前一个增 1。

#include <iostream>

int plusOne()
{
    static int s_state{ 3 }; // 仅在首次调用时初始化

    ++s_state;      // 修改状态
    return s_state; // 返回新状态对应的新数字
}

int main()
{
    std::cout << plusOne() << '\n';
    std::cout << plusOne() << '\n';
    std::cout << plusOne() << '\n';
    return 0;
}

输出：

4
5
6

该算法很简单：首次调用 plusOne() 时，s_state 被初始化为 3。随后通过修改状态并返回新值生成序列。

若算法在多次调用间保留信息，则称其为“有状态”；否则为“无状态”。本例中 plusOne() 是有状态算法，因为它使用 static 变量 s_state 保存上一次生成的数字。算法中的“状态”即指这些跨调用保持的变量当前值。

生成下一个数字的两步流程：

1. 根据当前状态（初始或上次保留）计算新状态；
2. 从新状态生成下一个输出数字。

该算法是“确定性”的：给定同一输入（初始值），总会产生相同输出序列。

伪随机数生成器（PRNG）
为模拟随机性，程序常使用伪随机数生成器。PRNG 是一种算法，其输出序列的统计特性近似随机数序列。

编写一个简单 PRNG 并不困难。下例 LCG16() 生成 100 个 16 位伪随机数：

#include <iostream>

// 仅作示例，请勿实际使用
unsigned int LCG16()
{
    static unsigned int s_state{ 0 }; // 首次调用初始化为 0

    s_state = 8253729 * s_state + 2396403; // 修改状态
    return s_state % 32768;                // 生成下一个数字
}

int main()
{
    for (int count{ 1 }; count <= 100; ++count)
    {
        std::cout << LCG16() << '\t';
        if (count % 10 == 0)
            std::cout << '\n';
    }
    return 0;
}

示例输出（略）——各数字相对前一位看似随机。
注意 LCG16() 与 plusOne() 结构相似：先以数学运算更新状态，再以新状态生成输出。
此算法质量不高（输出奇偶交替明显），但大多数 PRNG 均遵循类似模式，只是使用更复杂的状态与运算。

PRNG 的播种（Seeding）

PRNG 生成的“随机数”序列并不随机，与 plusOne() 一样完全确定。给定相同初始状态（如 0），每次运行都会得到相同序列。
为获得不同序列，必须改变初始状态；用于设定初始状态的值（或值集）称为随机种子（seed）。设置初始状态即称为“播种”。

关键洞察
由于 PRNG 的初始状态由种子决定，所有输出值均可从种子通过确定性算法计算得出。

示例程序：要求用户输入种子，然后基于该种子生成 10 个随机数（使用 LCG16()）。

#include <iostream>

unsigned int g_state{ 0 };

void seedPRNG(unsigned int seed)
{
    g_state = seed;
}

unsigned int LCG16()
{
    g_state = 8253729 * g_state + 2396403;
    return g_state % 32768;
}

void print10()
{
    for (int count{ 1 }; count <= 10; ++count)
        std::cout << LCG16() << '\t';
    std::cout << '\n';
}

int main()
{
    unsigned int x{};
    std::cout << "Enter a seed value: ";
    std::cin >> x;
    seedPRNG(x);
    print10();
    return 0;
}

三次运行示例：

• 输入 7 → 输出序列固定；
• 再次输入 7 → 序列相同；
• 输入 9876 → 序列不同。

种子质量与“欠播种”

若希望程序每次运行产生不同随机数，需在每次运行时变化种子。让用户输入种子并不理想，因为用户可能重复输入同一值。程序需自行产生随机化种子。然而，不能用 PRNG 为自身生成种子（循环依赖），而应使用专门设计来产生种子的算法，下一课将讨论并实现此类算法。

理论上，PRNG 能生成的唯一序列最大数量由其状态位数决定。例如，128 位状态的 PRNG 理论上可生成 2^128 条唯一序列。
但实际能生成的不同序列受限于程序可提供的唯一种子数量。若种子生成算法只能产生 4 个不同种子，则 PRNG 最多只能输出 4 种序列。

若 PRNG 未获得足够高质量种子位，则称其“欠播种”（underseeded）。欠播种可能导致：

• 连续运行生成的序列高度相关；
• 第 N 个随机数后某些值永远无法出现（例如，特定欠播种的梅森旋转算法首输出永远不会是 7 或 13）；
• 攻击者可由初始随机值反推种子，进而预测全部后续输出，从而作弊或破坏系统。

高级读者提示

理想种子应具备：

• 位数不少于 PRNG 状态位，使每位都可独立初始化；
• 每位独立随机；
• 0 与 1 均匀分布；
• 无恒 0 或恒 1 的“固定位”；
• 与历史种子低相关。

实践中，可能妥协：

• 大状态 PRNG（如梅森旋转 19937 位）难以提供等长高质量种子，故其设计为对少位种子仍具鲁棒性；
• 使用系统时钟等源时，高位时间位几乎固定。

不熟悉正确播种实践的开发者常仅用 32 位或 64 位值初始化 PRNG（C++ 标准随机库的设计无意中鼓励了这一点），导致严重欠播种。
通常，使用 64 字节高质量种子（若 PRNG 状态更小则可减少）足以满足非敏感用途（非统计模拟或密码学）的 8 字节随机值生成。

何为优质 PRNG？（选读）

优质 PRNG 应满足以下特性：

1. 均匀分布
   各数字出现概率应大致相等。可用直方图检验：用“”表示出现次数。
   示例：生成 1–6 的 36 个数，理想直方图应各 6 个“”。
   若分布不均，例如 6 出现过多，则游戏掉落稀有物品概率高于设计值，破坏平衡。

2. 不可预测性
   即使看似随机的序列也可能被分析破解。例如，仅凭 LCG16() 的几个输出即可推算其常数，进而预测全部后续值。若在线博彩系统使用可预测 PRNG，用户可据此必胜，导致破产。

3. 高维分布良好
   输出应覆盖整个取值范围，避免先集中低值后集中高值等偏差。

4. 周期足够长
   所有 PRNG 都周期重复。周期越短，重复越快。示例 PRNG 周期仅 14，表现极差。
   优质 PRNG 应对所有种子均提供长周期，设计难度极高。

5. 效率
   大多 PRNG 状态 < 4096 字节，内存非瓶颈；状态越大越易欠播种且初始化更慢。
   生成下一个数需混合内部状态的数学运算耗时不同，高频生成时影响显著。

PRNG 算法种类繁多
历史上出现大量 PRNG 算法（见维基百科）。每算法各有优劣，需按应用场景选择。
许多旧算法已不符合现代标准，使用高性能算法与旧算法同样简单，故应避免劣质算法。

C++ 中的随机化

C++ 通过头文件 提供随机化功能。截至 C++20，库内包含 6 个 PRNG 族：

*状态大小为近似值
没有理由使用 knuth_b、default_random_engine 或 rand()。
截至 C++20，梅森旋转是唯一兼具中等性能与质量的 PRNG。

高级提示

PracRand 测试常用于评估 PRNG 性能与质量（检测偏差）。SmallCrush、Crush、BigCrush 亦用于类似目的。
可在该网站查看 C++20 支持的所有 PRNG 的 PracRand 报告。

我们该用梅森旋转吗？

大多数情况下，梅森旋转在性能与质量上均可接受。
然而，按现代标准，梅森旋转已显老旧：其输出在观测 624 个数后即可被预测，故不适合需不可预测性的场景。

若应用要求最高质量（如统计模拟）、极致速度或不可预测性（如密码学），应使用第三方库。
当前流行选择：

• 非密码学：Xoshiro 族、WyRand；
• 密码学（不可预测）：ChaCha 族。

理论已够让人眼花缭乱，下一节我们讨论如何在 C++ 中用梅森旋转实际生成随机数。