随机数生成简介

本节阅读量:

生成随机数的能力在某些类型的程序中非常有用，特别是在需要解密游戏、统计建模程序和加密应用程序中。以游戏为例——没有随机事件，怪物总是以相同的方式攻击你，你总是会找到相同的宝藏，地牢布局永远不会改变，等等……这不会是一个非常好玩的游戏。

在现实生活中，我们经常通过做诸如抛硬币、掷骰子或洗牌等事情来产生随机化。这些事件实际上不是随机的，但因为它们涉及如此多的物理变量（例如重力、摩擦力、空气阻力、动量等），以至于它们几乎不可能预测或控制，并且（除非你是魔术师）产生的结果在所有意图和目的上都是随机的。

然而，计算机不能抛硬币、掷骰子或洗牌。现代计算机生活在一个受控的电子世界中，所有的东西都是二进制的（0或1）。就其本质而言，计算机被设计为产生尽可能可预测的结果。当你告诉计算机计算2+2时，你总是希望答案是4。而不是偶尔产生3或5。

因此，计算机通常无法生成真正的随机数（至少只通过软件）。相反，现代程序通常使用一些算法来模拟随机性。

在这节课中，我们将介绍程序中如何生成随机数背后的许多理论，并介绍一些将在以后的课程中使用的术语。

算法（algorithm）和状态

首先，介绍算法和状态的概念。

算法是一个有限的指令序列，可以遵循它来解决某些问题或产生一些有用的结果。

例如，假设您的老板给了您一个小文本文件，其中包含一组未排序的名称（每行一个），并要求您对列表进行排序。由于列表很小，因此您决定手动排序。有多种方法可以对列表进行排序，但您可以这样做：

创建新的空列表以保存排序的结果
扫描未排序名称的列表以查找按字母顺序排在第一位的名称
从未排序列表中剪切该名称，并将其粘贴到已排序列表的底部
重复前面的两个步骤，直到未排序列表上没有更多的名称

上述一组步骤描述了排序算法（使用自然语言）。本质上，算法是可重用的——如果您的老板明天要求您对另一个列表进行排序，那么可以将相同的算法应用于新的列表。

由于计算机可以比更快地执行指令和操作数据，因此算法通常使用编程语言编写，使我们能够自动化任务。在C++中，算法通常被实现为可重用的函数。

下面是一个生成数字序列的简单算法，其中每次数字递增1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <iostream>

int plusOne()
{
    static int s_state { 3 }; // 只在函数被调用时初始化一次

    // 产出下一个数字

    ++s_state;      // 首先修改s_state
    return s_state; // 返回修改后结果
}

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

    return 0;
}

这将打印：

这个算法相当简单。第一次调用plusOne()时，s_state初始化为值3。然后生成并返回序列中的下一个数字。

如果算法在调用之间保留了一些信息，则认为该算法是有状态的。相反，无状态算法不存储任何信息（并且必须在调用它时提供它所需的所有信息）。plusOne()函数是有状态的，因为它使用静态变量s_state存储生成的数字。当应用于算法时，术语“状态”是指保存在有状态变量中的当前值（在不同调用之间保留的值）。

为了生成序列中的下一个数字，plusOne这个算法分两步：

首先，修改当前状态（初始值，或从之前的调用保留的值）以生成新状态。
然后，返回新状态。

这个算法被认为是确定性的，这意味着对于给定的输入（相同的初始值），它将始终产生相同的输出序列。

伪随机数生成器（PRNGs）

为了模拟随机性，程序通常使用伪随机数生成器（pseudo-random number generator，PRNG）。这是一种模拟随机数序列生成的算法。

编写基本的PRNG算法很容易。下面是一个生成100个16位伪随机数的简短示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#include <iostream>

// 这只是演示用，实际不要使用
unsigned int LCG16() // 我们自己的 PRNG
{
    static unsigned int s_state{ 5323 };

    // 产生下一个数字

    // 使用大的常量，和有意的数字溢出
    // 让别人不太容易猜到，下一个产出的数字

    s_state = 8253729 * s_state + 2396403; // 修改s_state
    return s_state % 32768; // 使用s_state，算出伪随机数序列的下一位
}

int main()
{
    // 打印100个随机数
    for (int count{ 1 }; count <= 100; ++count)
    {
        std::cout << LCG16() << '\t';

        // 每打印10个，换行一下
        if (count % 10 == 0)
            std::cout << '\n';
    }

    return 0;
}

该程序的结果是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


23070   27857   22756   10839   27946   11613   30448   21987   22070   1001
27388   5999    5442    28789   13576   28411   10830   29441   21780   23687
5466    2957    19232   24595   22118   14873   5932    31135   28018   32421
14648   10539   23166   22833   12612   28343   7562    18877   32592   19011
13974   20553   9052    15311   9634    27861   7528    17243   27310   8033
28020   24807   1466    26605   4992    5235    30406   18041   3980    24063
15826   15109   24984   15755   23262   17809   2468    13079   19946   26141
1968    16035   5878    7337    23484   24623   13826   26933   1480    6075
11022   19393   1492    25927   30234   17485   23520   18643   5926    21209
2028    16991   3634    30565   2552    20971   23358   12785   25092   30583

看起来每个数字似乎都是相当随机的。

请注意，LCG16()与上面的plusOne()示例非常相似！此外，可以向LCG16()传递一个用于初始化状态的初始值。然后，（通过应用一些数学运算）修改当前状态以产生新状态，并且序列中的下一个数是从该新状态生成的。

事实证明，这个特定的算法不太适合作为随机数生成器（请注意每个结果，在偶数和奇数之间交替——这不是很随机！）。但大多数PRNG的工作方式类似于LCG16()——它们通常只使用更多的状态变量和更复杂的数学运算，以生成更高质量的结果。

指定PRNG的种子

由PRNG生成的“随机数”序列根本不是随机的。就像plusOne()函数一样，LCG16()结果也是确定性的。一旦状态被初始化，LCG16()（和所有其他PRNG）将生成相同的输出序列。

当实例化PRNG时，可以提供称为随机种子（或简称种子）的初始值（或一组值）来初始化PRNG的状态。

大多数产生高质量结果的PRNG使用至少16个字节的状态，如果不是明显更多的话。然而，如果种子的输入状态大小，小于PRNG的内部状态，我们说PRNG的种子不足。

理想情况下，状态中的每个比特都是从相等大小的种子初始化的，并且种子中的每个位都是以某种方式独立确定的。然而，如果PRNG的种子不足，则需要从种子中的相同比特初始化PRNG内部状态中的一些比特。如果PRNG的种子严重不足（意味着种子的大小比状态的大小小得多），则PRNG产生的随机结果的质量可能会受到影响。

关键点

PRNG产生的所有值的序列都是从种子值确定地计算出来的。

什么是好的PRNG？（选读）

为了成为一个好的PRNG算法，需要展示许多特性：

PRNG应以近似相同的概率生成每个数字。

这称为分布均匀性。如果某些数字的生成频率高于其他数字，则使用PRNG的程序的结果将有偏差！为了检查分布均匀性，可以使用直方图。直方图是一个图表，它跟踪每个数字的生成次数。这里使用*符号来表示给定的数字的生成次数。

考虑一个生成1到6之间的数字的PRNG算法。如果生成36个数字，则具有分布均匀性的PRNG应生成如下所示的直方图：

1
2
3
4
5
6


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|****
2|********
3|******
4|********
5|******
6|****

假设您正在尝试为游戏编写随机项生成器。当怪物被杀死时，生成一个介于1和6之间的随机数，如果结果是6，怪物将产出一个稀有物品。您预计这种情况发生的几率为1/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生成的前100个数字：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

你会注意到它生成了9作为第二个数字，再次作为第十六个数字，然后每隔14个数字。该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++中的随机数

C++中的随机化功能可以通过标准库的头文件。在随机库中，有6个PRNG系列可供使用（从C++20开始）：

类型	算法	重复周期	内部状态大小	性能	结果质量	是否应该使用
minstd_rand minstd_rand0	Linear congruential generator	2^31	4字节	差	差	否
mt19937 mt19937_64	Mersenne twister	2^19937	2500字节	好	好	看情况而定
ranlux24 ranlux48	Subtract and carry	10^171	96字节	差	好	否
knuth_b	Shuffled linear congruential generator	2^31	1028字节	差	差	否
default_random_engine	上面的任意一种	根据实现而定	根据实现而定	?	?	否
rand()	Linear congruential generator	2^31	4字节	差	差	否

没有理由使用knuth_b、default_random_engine或rand()（这是为与C兼容而提供的随机数生成器）。

截至C++20，Mersenne Twister算法是C++附带的唯一一个性能和质量都不错的PRNG。

所以我们应该用Mersenne Twister，对吧？

可能吧。对于大多数应用，Mersenne Twister在性能和质量方面都很好。

然而，值得注意的是，按照现代PRNG标准，Mersenne Twister有点过时。Mersenne Twister最大的问题是，在看到624个生成的数字后，它的结果可以进行预测，这使得它不适用于需要不可预测性的应用。

如果您开发的应用程序需要最高质量的随机结果（例如统计模拟）、生成速度很快，或不可预测性很重要的应用程序（例如密码学），则需要使用第三方库。

截至编写时的流行选择：

Xoshiro 或 Wyrand，用于非加密的 PRNGs.。
Chacha，加密（不可预测）的PRNG。

现在这些就足够了。下节讨论如何在C++中使用Mersenne Twister实际生成随机数。

8.11 提前退出程序

8.13 使用Mersenne Twister生成随机数