生成随机数的能力在某些类型的程序中非常有用，尤其是在游戏、统计建模程序以及需要加密和解密内容的密码学应用程序中。以游戏为例——如果没有随机事件，怪物总是会以相同的方式攻击你，你总是会找到相同的宝藏，地牢布局永远不会改变，等等……这不会是一款非常好的游戏。
在现实生活中，我们经常通过抛硬币、掷骰子或洗牌等方式来产生随机性。这些事件实际上并非随机，但它们涉及如此多的物理变量（例如重力、摩擦力、空气阻力、动量等），以至于变得几乎无法预测或控制，并且（除非你是魔术师）产生的结果在所有意图和目的上都是随机的。
然而，计算机并非旨在利用物理变量——你的计算机无法抛硬币、掷骰子或洗真正的牌。现代计算机生活在一个受控的电子世界中，一切都是二进制的（0 或 1），没有中间值。就其本质而言，计算机旨在产生尽可能可预测的结果。当你告诉计算机计算 2 + 2 时，你总是希望答案是 4，而不是偶尔出现 3 或 5。
因此，计算机通常无法生成真正的随机数（至少通过软件）。相反，现代程序通常使用算法来模拟随机性。
在本课程中，我们将深入探讨程序中随机数生成背后的许多理论，并介绍一些我们将在未来课程中使用的术语。
算法与状态
首先，让我们回顾一下算法和状态的概念。
**算法**是一系列有限的指令，可以遵循这些指令来解决某个问题或产生一些有用的结果。
例如，假设你的老板给你一个包含一堆未排序名称（每行一个）的小文本文件，并要求你对列表进行排序。由于列表很小，而且你预计不会经常这样做，所以你决定手动排序。排序列表有多种方法，但你可能会这样做：
- 创建一个新的空列表来保存排序结果
- 扫描未排序名称列表以找到按字母顺序排列第一个的名称
- 从未排序列表中剪切该名称并将其粘贴到已排序列表的底部
- 重复前两个步骤，直到未排序列表中没有更多名称
以上步骤描述了一个排序算法（使用自然语言）。本质上，算法是可重用的——如果你的老板明天让你排序另一个列表，你只需将相同的算法应用于新列表即可。
由于计算机执行指令和处理数据的速度比我们快得多，算法通常使用编程语言编写，从而使我们能够自动化任务。在 C++ 中，算法通常实现为可重用函数。
这是一个简单的算法，用于生成一个数字序列，其中每个连续的数字都递增 1
#include <iostream>
int plusOne()
{
static int s_state { 3 }; // only initialized the first time this function is called
// Generate the next number
++s_state; // first we modify the state
return s_state; // then we use the new state to generate the next number in the sequence
}
int main()
{
std::cout << plusOne() << '\n';
std::cout << plusOne() << '\n';
std::cout << plusOne() << '\n';
return 0;
}这会打印
4 5 6
这个算法非常简单。我们第一次调用 plusOne() 时，s_state 初始化为值 3。然后生成并返回输出序列中的下一个数字。
如果一个算法在不同调用之间保留一些信息，则称其为**有状态**的。相反，**无状态**算法不存储任何信息（并且在每次调用时都必须为其提供所有需要处理的信息）。我们的 plusOne() 函数是有状态的，因为它使用静态变量 s_state 来存储上一个生成的数字。当应用于算法时，术语**状态**指的是有状态变量（那些在不同调用之间保留的变量）中保存的当前值。
为了生成序列中的下一个数字，我们的算法使用两步过程
- 首先，修改当前状态（从起始值初始化，或从先前调用保留）以产生新状态。
- 然后，从新状态生成序列中的下一个数字。
我们的算法被认为是**确定性**的，这意味着对于给定的输入（为 start 提供的值），它将始终产生相同的输出序列。
伪随机数生成器 (PRNG)
为了模拟随机性，程序通常使用伪随机数生成器。**伪随机数生成器 (PRNG)** 是一种算法，它生成一个数字序列，其属性模拟随机数序列。
编写一个基本的 PRNG 算法很简单。这是一个简短的 PRNG 示例，它生成 100 个 16 位伪随机数
#include <iostream>
// For illustrative purposes only, don't use this
unsigned int LCG16() // our PRNG
{
static unsigned int s_state{ 0 }; // only initialized the first time this function is called
// Generate the next number
// We modify the state using large constants and intentional overflow to make it hard
// for someone to casually determine what the next number in the sequence will be.
s_state = 8253729 * s_state + 2396403; // first we modify the state
return s_state % 32768; // then we use the new state to generate the next number in the sequence
}
int main()
{
// Print 100 random numbers
for (int count{ 1 }; count <= 100; ++count)
{
std::cout << LCG16() << '\t';
// If we've printed 10 numbers, start a new row
if (count % 10 == 0)
std::cout << '\n';
}
return 0;
}这个程序的输出是
4339 838 25337 15372 6783 2642 6021 19992 14859 26462 25105 13860 28567 6762 17053 29744 15139 9078 14633 2108 7343 642 17845 29256 5179 14222 26689 12884 8647 17050 8397 18528 17747 9126 28505 13420 32479 23218 21477 30328 20075 26558 20081 3716 13303 19146 24317 31888 12163 982 1417 16540 16655 4834 16917 23208 26779 30702 5281 19124 9767 13050 32045 4288 31155 17414 31673 11468 25407 11026 4165 7896 25291 26654 15057 26340 30807 31530 31581 1264 9187 25654 20969 30972 25967 9026 15989 17160 15611 14414 16641 25364 10887 9050 22925 22816 11795 25702 2073 9516
每个数字似乎都与前一个数字非常随机。
请注意 LCG16() 与我们上面的 plusOne() 示例是多么相似！状态最初设置为值 0。然后为了在输出序列中生成下一个数字，修改当前状态（通过应用一些数学运算）以产生新状态，并从该新状态生成序列中的下一个数字。
事实证明，这种特定算法作为随机数生成器并不十分好（请注意每个结果在偶数和奇数之间交替——这不是很随机！）。但大多数 PRNG 的工作方式与 LCG16() 相似——它们通常只是使用更多的状态变量和更复杂的数学运算来生成质量更好的结果。
为 PRNG 播种
PRNG 生成的“随机数”序列根本不是随机的。就像我们的 plusOne() 函数一样，LCG16() 也是确定性的。给定某个初始状态值（例如 0），PRNG 每次都会生成相同的数字序列。如果你运行上述程序 3 次，你会发现它每次都生成相同的值序列。
为了生成不同的输出序列，PRNG 的初始状态需要改变。用于设置 PRNG 初始状态的值（或一组值）称为**随机种子**（或简称**种子**）。当 PRNG 的初始状态使用种子设置时，我们说它已经被**播种**。
关键见解
由于 PRNG 的初始状态是从种子值设置的，因此 PRNG 将产生的所有值都是从种子值确定性计算的。
种子值通常由使用 PRNG 的程序提供。这是一个示例程序，它从用户请求一个种子值，然后使用该种子值（使用我们的 LCG16() 函数）生成 10 个随机数。
#include <iostream>
unsigned int g_state{ 0 };
void seedPRNG(unsigned int seed)
{
g_state = seed;
}
// For illustrative purposes only, don't use this
unsigned int LCG16() // our PRNG
{
// We modify the state using large constants and intentional overflow to make it hard
// for someone to casually determine what the next number in the sequence will be.
g_state = 8253729 * g_state + 2396403; // first we modify the state
return g_state % 32768; // then we use the new state to generate the next number in the sequence
}
void print10()
{
// Print 10 random numbers
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); // seed our PRNG
print10(); // generate 10 random values
return 0;
}这是该程序的 3 次运行示例
Enter a seed value: 7 10458 3853 16032 17299 10726 32153 19116 7455 242 549
Enter a seed value: 7 10458 3853 16032 17299 10726 32153 19116 7455 242 549
Enter a seed value: 9876 24071 18138 27917 23712 8595 18406 23449 26796 31519 7922
请注意，当我们提供相同的种子值时，我们得到相同的输出序列。如果我们提供不同的种子值，我们得到不同的输出序列。
种子质量与欠播种
如果我们希望程序每次运行时都生成不同的随机数，那么我们需要一种方法来在程序每次运行时改变种子。要求用户提供一个种子值并不好，因为他们每次都可以输入相同的值。程序确实需要一种方法来在每次运行时生成一个随机的种子值。不幸的是，我们不能使用 PRNG 来生成随机种子，因为我们需要一个随机种子来生成随机数。相反，我们通常会使用一种旨在生成种子值的种子生成算法。我们将在下一课中讨论（并实现）此类算法。
PRNG 可以生成的独特序列的理论最大数量由 PRNG 状态中的位数决定。例如，一个具有 128 位状态的 PRNG 理论上可以生成多达 2^128 (340,282,366,920,938,463,463,374,607,431,768,211,456) 个独特的输出序列。这非常多！
然而，实际生成哪个输出序列取决于 PRNG 的初始状态，而这又由种子决定。因此，实际上，PRNG 实际可以生成的独特输出序列数量受限于使用 PRNG 的程序可以提供的独特种子值数量。例如，如果一个特定的种子生成算法只能生成 4 个不同的种子值，那么 PRNG 最多只能生成 4 个不同的输出序列。
如果未向 PRNG 提供足够位数的优质种子数据，我们称其为**欠播种**。欠播种的 PRNG 可能会开始产生质量在某种程度上受损的随机结果——欠播种越严重，结果的质量就会越差。
例如，欠播种的 PRNG 可能会出现以下任何问题：
- 连续运行生成的随机序列之间可能存在高度相关性。
- 在生成第 N 个随机数时，某些值将永远无法生成。例如，以特定方式欠播种的 Mersenne Twister 永远不会将 7 或 13 作为其第一个输出。
- 有人可能会根据产生的初始随机值（或前几个随机值）猜测种子。这将使他们能够生成生成器将产生的所有未来随机数。这可能允许他们作弊或操纵系统。
致进阶读者
一个理想的种子应具有以下特点：
- 种子应包含至少与 PRNG 状态相同位数的比特，以便 PRNG 状态中的每个比特都可以由种子中独立的比特初始化。
- 种子中的每个比特都应独立随机化。
- 种子应包含在所有比特中良好混合的 0 和 1。
- 种子中不应有始终为 0 或始终为 1 的比特。这些“固定比特”不提供任何价值。
- 种子应与先前生成的种子相关性较低。
在实践中，我们可能会在其中一些特性上妥协。一些 PRNG 具有巨大的状态（例如，Mersenne Twister 的状态有 19937 位），生成如此大的高质量种子可能很困难。因此，具有大状态的 PRNG 通常被设计为能够抵御用较少位数进行播种。固定位也很常见。例如，如果我们将系统时钟作为种子的一部分，我们将得到一些固定位，因为表示更大时间单位（例如年份）的位实际上是固定的。
不熟悉正确播种实践的开发者通常会尝试使用单个 32 位或 64 位值来初始化 PRNG（不幸的是，C++ 标准随机库的设计无意中鼓励了这一点）。这通常会导致严重欠播种的 PRNG。
用 64 字节高质量种子数据（如果 PRNG 状态较小则更少）播种 PRNG 通常足以促进生成 8 字节随机值以用于非敏感用途（例如，非统计模拟或加密）。
什么是一个好的 PRNG？（可选阅读）
为了成为一个好的 PRNG，它需要表现出一些特性：
- PRNG 应该以大致相同的概率生成每个数字。
这被称为分布均匀性。如果某些数字比其他数字更频繁地生成，那么使用 PRNG 的程序的结果将会出现偏差！为了检查分布均匀性，我们可以使用直方图。直方图是一种图形，它跟踪每个数字生成的次数。由于我们的直方图是基于文本的，我们将使用 * 符号来表示给定数字生成的每次。
考虑一个生成 1 到 6 之间数字的 PRNG。如果我们生成 36 个数字，一个具有分布均匀性的 PRNG 应该生成一个看起来像这样的直方图：
1|****** 2|****** 3|****** 4|****** 5|****** 6|******
一个以某种方式存在偏差的 PRNG 将生成一个不均匀的直方图，像这样：
1|*** 2|****** 3|****** 4|****** 5|****** 6|*********
或者这样
1|**** 2|******** 3|****** 4|******** 5|****** 6|****
甚至可能是这样
1|******* 2|******** 3|******* 4|******** 5| 6|******
假设你正在为一款游戏编写一个随机物品生成器。当怪物被杀死时，你的代码会生成一个 1 到 6 之间的随机数，如果结果是 6，怪物将掉落稀有物品而不是普通物品。你期望这种情况发生的几率为六分之一。但如果底层的 PRNG 不均匀，并且生成的 6 远多于应有的数量（如上面的第二个直方图），你的玩家最终会得到比你预期更多的稀有物品，这可能会使你的游戏难度变得微不足道，或者扰乱你的游戏内经济。
找到能产生均匀结果的 PRNG 算法很困难。
- 生成序列中下一个数字的方法不应可预测。
例如，考虑以下 PRNG 算法：return ++num。这个 PRNG 是完全均匀的，但它也是完全可预测的——作为随机数序列，它并不是很有用！
即使是肉眼看起来随机的数字序列（例如上面 LCG16() 的输出），对于有动机的人来说也可能轻易预测。通过检查上面 LCG16() 函数生成的几个数字，可以确定用于修改状态的常量（8253729 和 2396403）。一旦知道了这些，计算该 PRNG 将生成的所有未来数字就变得轻而易举了。
现在，想象一下你正在运营一个博彩网站，用户可以下注 100 美元。你的网站然后生成一个 0 到 32767 之间的随机数。如果数字大于 20000，客户赢，你返还双倍赌注。否则，他们输，你保留赌注。由于客户只赢 12767/32767 (39%) 的时间，你的网站应该能赚大钱，对吧？然而，如果客户能够确定接下来将生成哪些数字，那么他们就可以策略性地下注，以便他们总是（或通常）赢。恭喜，现在你可以申请破产了！
- PRNG 应该具有良好的数字维度分布。
这意味着 PRNG 应该在所有可能的随机结果范围内返回数字。例如，PRNG 应该看起来随机地生成低数字、中等数字、高数字、偶数和奇数。
一个先返回所有低数字，然后返回所有高数字的 PRNG 可能均匀且不可预测，但它仍然会导致有偏差的结果，尤其是当你实际使用的随机数数量很少时。
- PRNG 应该对所有种子具有较长的周期
所有 PRNG 都是周期性的，这意味着在某个点，生成的数字序列将开始重复。在 PRNG 开始重复之前序列的长度称为**周期**。
例如，以下是一个周期性较差的 PRNG 生成的前 100 个数字：
112 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9 130 97 64 31 152 119 86 53 20 141 108 75 42 9
你会注意到它在第 2 个数字时生成了 9，在第 16 个数字时又生成了 9，然后每 14 个数字之后都会生成 9。这个 PRNG 陷入重复生成以下序列的循环中：9-130-97-64-31-152-119-86-53-20-141-108-75-42-（重复）。
发生这种情况是因为 PRNG 是确定性的。一旦 PRNG 的状态与先前的状态相同，PRNG 就会开始生成它以前生成过的相同输出序列——从而导致循环。
一个好的 PRNG 应该对所有种子编号都有一个长周期。设计满足此属性的算法可能非常困难——许多 PRNG 仅对某些种子具有长周期，而对其他种子则没有。如果用户碰巧选择了一个导致短周期状态的种子，那么如果需要许多随机数，PRNG 将无法很好地工作。
- PRNG 应该高效
大多数 PRNG 的状态大小小于 4096 字节，因此总内存使用通常不是问题。然而，内部状态越大，PRNG 欠播种的可能性就越大，并且初始播种速度就越慢（因为需要初始化的状态越多）。
其次，为了生成序列中的下一个数字，PRNG 必须通过应用各种数学运算来混合其内部状态。这需要的时间可能因 PRNG 和架构而异（有些 PRNG 在某些架构上表现优于其他架构）。如果你只定期生成随机数，这无关紧要，但如果你需要大量随机性，这可能会产生巨大影响。
有许多不同种类的 PRNG 算法
多年来，已经开发了许多不同类型的 PRNG 算法（维基百科有一个很好的列表在这里）。每个 PRNG 算法都有其优缺点，这可能使其更适合或不适合特定应用程序，因此为你的应用程序选择正确的算法很重要。
许多 PRNG 现在被现代标准认为相对较差——而且没有理由使用性能不佳的 PRNG，因为它与使用性能良好的 PRNG 一样容易。
C++ 中的随机化功能可以通过标准库的 <random> 头文件访问。在随机库中，有 6 种 PRNG 系列可供使用（截至 C++20）：
| 类型名称 | 系列 | 周期 | 状态大小* | 性能 | 质量 | 我应该使用这个吗？ |
|---|---|---|---|---|---|---|
| minstd_rand minstd_rand0 | 线性同余生成器 | 2^31 | 4 字节 | 差 | 极差 | 否 |
| mt19937 mt19937_64 | Mersenne Twister | 2^19937 | 2500 字节 | 不错 | 不错 | 可能（参见下一节） |
| ranlux24 ranlux48 | 减法带借位 | 10^171 | 96 字节 | 极差 | 好 | 否 |
| knuth_b | 洗牌线性同余生成器 | 2^31 | 1028 字节 | 极差 | 差 | 否 |
| default_random_engine | 以上任意（实现定义） | 不同 | 不同 | ? | ? | 否2 |
| rand() | 线性同余生成器 | 2^31 | 4 字节 | 差 | 极差 | 否否 |
没有理由使用 knuth_b、default_random_engine 或 rand()（这是一个为兼容 C 语言而提供的随机数生成器）。
截至 C++20，Mersenne Twister 算法是 C++ 自带的唯一一种兼具良好性能和质量的 PRNG。
致进阶读者
一个名为 PracRand 的测试通常用于评估 PRNG 的性能和质量（以确定它们是否存在不同类型的偏差）。你可能还会看到对 SmallCrush、Crush 或 BigCrush 的引用——这些是有时用于相同目的的其他测试。
如果你想看看 Pracrand 的输出是什么样子，这个网站提供了 C++20 支持的所有 PRNG 的输出。
那么我们应该使用 Mersenne Twister，对吧？
可能吧。对于大多数应用程序来说，Mersenne Twister 在性能和质量方面都是不错的选择。
然而，值得注意的是，按照现代 PRNG 标准，Mersenne Twister 有点过时了。Mersenne Twister 最大的问题是，在看到 624 个生成的数字后，它的结果就可以被预测，这使得它不适用于任何需要不可预测性的应用程序。
如果您正在开发需要最高质量随机结果（例如统计模拟）、最快结果或不可预测性很重要（例如加密）的应用程序，则需要使用第三方库。
截至撰写本文时，流行选择包括：
- Xoshiro 系列和 Wyrand 用于非加密 PRNG。
- Chacha 系列用于加密（不可预测）PRNG。
好了，你的眼睛可能已经流血了，理论就到此为止。让我们讨论一下如何在 C++ 中实际使用 Mersenne Twister 生成随机数。