使用梅森旋转算法生成随机数

在上一课随机数生成导论中，我们介绍了随机数生成的概念，并讨论了程序中通常使用 PRNG 算法来模拟随机性。

本课将演示如何在程序中生成随机数。为使用 C++ 的任何随机化功能，需包含标准库头文件 <random>。

在 C++ 中使用梅森旋转生成随机数

梅森旋转（Mersenne Twister）PRNG 除名字悦耳外，也是跨语言最流行的 PRNG。尽管以今日标准略显老旧，但其结果质量高、性能尚可。<random> 提供两种梅森旋转类型：

mt19937：生成 32 位无符号整数
mt19937_64：生成 64 位无符号整数

使用示例：

#include <iostream>
#include <random> // for std::mt19937

int main()
{
    std::mt19937 mt{}; // 实例化 32 位梅森旋转

    // 输出若干随机数
    for (int count{ 1 }; count <= 40; ++count)
    {
        std::cout << mt() << '\t'; // 生成一个随机数

        if (count % 5 == 0)
            std::cout << '\n';
    }

    return 0;
}

示例输出（略）：

3499211612  581869302   3890346734  …

说明：

包含 <random> 以获取所有随机功能。
std::mt19937 mt{} 实例化 32 位梅森旋转。
调用 mt() 生成一个 32 位无符号随机整数。

补充说明：
mt() 是 mt.operator() 的简写形式，返回序列中的下一个随机值，语法简洁。

用梅森旋转掷骰子

32 位 PRNG 产生 0–4 294 967 295 之间的数，但我们常常需要更小范围。若模拟六面骰，需 1–6 之间的均匀整数；若模拟剑伤害 7–11 点，则需 7–11 之间的随机数。

PRNG 自身无法直接限制范围。我们需要将 PRNG 输出映射到所需区间，并保证均匀无偏。<random> 通过“随机数分布”解决此问题。

补充说明：
对统计爱好者：随机数分布即接受 PRNG 值作为输入的概率分布。

<random> 提供多种分布，其中“均匀分布”最常用：在区间 [X, Y] 内等概率生成整数。

示例：使用均匀分布模拟掷六面骰：

#include <iostream>
#include <random> // for std::mt19937 和 std::uniform_int_distribution

int main()
{
    std::mt19937 mt{};

    // 创建可复用的 1–6 均匀整数分布
    std::uniform_int_distribution die6{ 1, 6 }; // C++14 起可省略模板实参

    for (int count{ 1 }; count <= 40; ++count)
    {
        std::cout << die6(mt) << '\t'; // 掷骰一次

        if (count % 10 == 0)
            std::cout << '\n';
    }

    return 0;
}

输出示例（略）：

3   1   3   6   5   2   6   6   1   2
...

与前例相比：

创建 die6 均匀分布对象；
调用 die6(mt) 而非 mt()，得到 1–6 的随机数。

上述程序并不真正随机

若多次运行，会发现输出序列完全相同！虽然序列内部相邻数字看似随机，但整段序列固定。这对猜数字游戏毫无趣味。

原因：我们值初始化梅森旋转，每次运行使用同一固定种子，于是产生同一序列。
为解决此问题，需选用每次运行都不同的种子。常用方法：

使用系统时钟
使用系统随机设备

以系统时钟播种

除非两次运行在同一纳秒，否则当前时间不同，可用作种子。C/C++ 传统上使用 std::time()；现代 C++ 使用 <chrono> 提供的时钟。

#include <iostream>
#include <random>
#include <chrono>

int main()
{
    // 使用 steady_clock 播种
    std::mt19937 mt{
        static_cast<std::mt19937::result_type>(
            std::chrono::steady_clock::now().time_since_epoch().count()
        )
    };

    std::uniform_int_distribution die6{ 1, 6 };

    for (int count{ 1 }; count <= 40; ++count)
    {
        std::cout << die6(mt) << '\t';
        if (count % 10 == 0) std::cout << '\n';
    }

    return 0;
}

缺点：若程序启动间隔极短，种子差异小，统计质量可能不足。
提示：std::chrono::high_resolution_clock 粒度更高，但可被用户回拨；steady_clock 不可调。

以 `std::random_device` 播种

<random> 提供 std::random_device，实现定义的 PRNG，通常向操作系统获取随机数。虽为“实现定义”，主流编译器已正确实现。

#include <iostream>
#include <random>

int main()
{
    std::mt19937 mt{ std::random_device{}() };

    std::uniform_int_distribution die6{ 1, 6 };

    for (int count{ 1 }; count <= 40; ++count)
    {
        std::cout << die6(mt) << '\t';
        if (count % 10 == 0) std::cout << '\n';
    }

    return 0;
}

注意：std::random_device 在极少数系统可能非随机（旧版 MinGW bug）。主流编译器已修复。

最佳实践
使用 std::random_device 为 PRNG 播种（除非目标平台实现有误）。

Q：std::random_device{}() 含义？
创建临时 std::random_device 对象并立即调用其 operator()，返回随机值作为种子，无需命名变量，语法简洁。

Q：既然 std::random_device 已随机，为何不用它代替梅森旋转？
因其实现定义，可能昂贵或阻塞；其随机池亦可能耗尽，影响系统其他程序。故推荐仅用于播种。

只播种一次

多数 PRNG 支持重新播种，但这会重置状态，导致随机性下降。一般不应重播。

最佳实践
对每个 PRNG 仅播种一次，勿重播。

常见错误示例：

int getCard()
{
    std::mt19937 mt{ std::random_device{}() }; // 每次调用都重新播种
    std::uniform_int_distribution card{ 1, 52 };
    return card(mt);
}

效率低且质量差。

梅森旋转的欠播种问题

梅森旋转内部状态需 19937 位（约 2493 字节，624 个 32 位整数）。

std::mt19937 分配 624 个整数；
std::mt19937_64 分配 312 个整数。

补充说明
std::mt19937 使用 std::uint_fast32_t，在 64 位平台可能为 64 位，导致占用翻倍。

前述示例仅用单个整数播种，严重欠播种。标准库会尽力填充剩余 623 个值，但无法“变魔术”。因此，用 32 位种子启动的 mt19937 永远不会首输 42。

解决方案（C++20 前）：

使用 std::seed_seq：
将已获得的若干随机整数传给 std::seed_seq，它会生成足够位数的无偏种子序列。
示例：

#include <iostream>
#include <random>

int main()
{
    std::random_device rd;
    std::seed_seq ss{ rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd() };
    std::mt19937 mt{ ss };
    std::uniform_int_distribution die6{ 1, 6 };

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

简洁易行，建议至少采用。
若给 std::seed_seq 624 个值则过慢且可能耗尽随机池。

使用状态更小的 PRNG：
许多优质 PRNG 仅 64/128 位状态，可用 8 个 std::random_device 值轻松初始化。

PRNG 预热

欠播种或低质量种子时，PRNG 初始输出质量可能不高。可通过“预热”丢弃前 N 个结果，使内部状态充分混合。通常丢弃数百至数千个值；周期越长，需丢弃越多。
std::mt19937 的种子初始化已含预热，无需手动进行。

补充说明
旧版 Visual Studio 的 rand() 曾因首值不够随机而需手动丢弃一次输出。

跨函数或文件的随机数使用（Random.h）

相关内容已移至 8.15 — 全局随机数（Random.h）。

调试使用随机数的程序

随机程序行为每次不同，调试困难。建议在调试时使用固定种子（如 5），确保每次运行一致。若某种子未触发错误，可递增种子直至复现，定位后再恢复真正播种方式。

随机数 FAQ

Q：随机数生成器每次输出相同序列？
→ 未正确播种或未播种，请确保每次运行使用不同种子。

Q：随机数生成器重复输出同一数字？
→ 可能在每次生成前重播或重新创建了生成器。