使用Mersenne Twister生成随机数

本节阅读量:

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

在本课中，将了解如何在程序中生成随机数。为了访问C++中的任何随机化功能，需要引用标准库的头文件。

使用Mersenne Twister在C++中生成随机数

Mersenne Twister PRNG除了有一个很好的名字外，可能是所有编程语言中最流行的PRNG。尽管按今天的标准来看，它有点老，但它通常产生高质量的结果，并具有良好的性能。随机库支持两种Mersenne Twister类型:

mt19937是一个Mersenne Twister算法，它生成32位无符号整数
mt19937_64是生成64位无符号整数的Mersenne Twister

使用Mersenne Twister非常简单:

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


#include <iostream>
#include <random> // 引入 std::mt19937

int main()
{
	std::mt19937 mt{}; // 初始化 一个32位的 Mersenne Twister

	// 打印一堆随机数
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << mt() << '\t'; // 产出一个随机数

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

	return 0;
}

这将产生以下结果:

1
2
3
4
5
6
7
8


3499211612      581869302       3890346734      3586334585      545404204
4161255391      3922919429      949333985       2715962298      1323567403
418932835       2350294565      1196140740      809094426       2348838239
4264392720      4112460519      4279768804      4144164697      4156218106
676943009       3117454609      4168664243      4213834039      4111000746
471852626       2084672536      3427838553      3437178460      1275731771
609397212       20544909        1811450929      483031418       3933054126
2747762695      3402504553      3772830893      4120988587      2163214728

首先，引入头文件，因为这是所有随机数功能的所在。接下来，我们通过语句std::mt19937 mt 实例化32位Mersenne Twister引擎。然后，每次希望生成随机的32位无符号整数时，调用mt()。

提示

由于mt是一个变量，您可能想知道mt()是什么意思。

在std::string简介中，展示了一个示例，其中调用了函数name.length()，该函数调用了std::string变量name上的length()函数。

mt()是用于调用函数mt.operator()的简明语法，对于这些PRNG类型，该函数被定义为返回序列中的下一个随机结果。使用operator()而不是命名函数的优点是，不需要记住函数的名称，并且打字更少。

使用Mersenne Twister掷骰子

32位PRNG将生成介于0和4294967295之间的随机数，但我们并不总是希望数字在该范围内。如果我们的程序是模拟棋盘游戏或骰子游戏，可能希望通过生成1到6之间的随机数来模拟六边形骰子的滚动。如果我们的程序是地牢冒险，并且玩家有一把对怪物造成7到11伤害的剑，每当玩家撞上怪物时，都希望生成7到11之间的随机数。

不幸的是，PRNG无法做到这一点。它们只能生成整个范围的数字。需要某种方法，将从PRNG输出的数字转换为想要的较小范围内的值（每个值发生的概率均等）。虽然我们可以自己编写一个函数来完成这项工作，但产生无偏差结果的函数并不是那么容易实现。

幸运的是，random库，支持指定随机数的分布（random number distribution）。

随机库有许多随机数分布器，除非进行统计分析，否则绝大多数都不会使用。有一个随机数分布非常有用:均匀分布（uniform distribution），它以相等的概率在两个数字X和Y（包括X和Y）之间产生输出。

旁白

随机数分布器，旨在将PRNG产出值作为输入，按照概率分布转换成对应的输出。

这里有一个类似于上面的程序，使用均匀分布器来模拟6面骰子的掷骰:

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


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

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

	// 创建一个均匀随机数分布器，可以将PRNGS的输出归一化到1 到 6 之间
	std::uniform_int_distribution die6{ 1, 6 }; // 对于 C++14, 可以写成 std::uniform_int_distribution<> die6{ 1, 6 };

	// 打印一堆随机数
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << die6(mt) << '\t'; // 产出一个投掷结果

		// 每输出10个数字，换行
		if (count % 10 == 0)
			std::cout << '\n';
	}

	return 0;
}

这将产生以下结果:

1
2
3
4


3       1       3       6       5       2       6       6       1       2
2       6       1       1       6       1       4       5       2       5
6       2       6       2       1       3       5       4       5       6
1       4       2       3       1       2       2       6       2       1

与前一个示例相比，此示例中只有两个值得注意的差异。首先，创建了一个均匀分布变器（名为die6）来生成1到6之间的数字。其次，现在调用die6(mt)来生成1到6之间的值，而不是调用mt()来生成32位无符号随机整数。

上面的程序并不像看上去那样随机

尽管上面的掷骰子示例的结果非常随机，但该程序存在一个主要缺陷。运行该程序3次，看看您是否可以找出它是什么?

如果您多次运行该程序，您将注意到它每次都打印相同的数字！虽然序列中的每个数字相对于前一个是随机的，但整个序列根本不是随机的！程序的每次运行都会产生完全相同的结果。

假设您正在编写一个猜数字游戏，其中用户有10次尝试猜测随机选取的数字，计算机会告诉用户他们的猜测是太高还是太低。如果计算机每次都选取相同的随机数，那么游戏在第一次玩过之后就不会有趣了。因此，让我们更深入地了解为什么会发生这种情况，以及如何修复它。

在上一课中，介绍了PRNG序列中的每个数都是确定性的。并且从种子值初始化PRNG的状态。因此，给定任何起始种子数，PRNG将始终从该种子生成相同的数字序列作为结果。

因为对Mersenne Twister进行值初始化，所以每次运行程序时，它都使用相同的种子进行初始化。因为种子是相同的，所以生成的随机数也是相同的。

为了使整个序列在程序每次运行时都以不同的方式随机分布，需要选择一个不是固定数字的种子。第一个可能想到的答案是，我们的种子需要一个随机数！这是一个好主意，但如果需要一个随机数来生成随机数，那么我们就陷入了第二十二条军规。

当然，我们真的不需要种子是随机数——只需要选择在程序每次运行时发生变化的东西。然后，PRNG从该种子生成唯一的伪随机数序列。

通常使用两种方法来执行此操作:

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

使用系统时钟播种

每次运行程序时，有一件事是不同的？除非您设法在完全相同的时间点运行程序两次，否则当前启动时间不同。因此，如果我们使用当前时间作为种子值，那么程序每次运行时都会产生一组不同的随机数。C和C++有很长的使用当前时间播种PRNG的历史（使用std::time()函数），因此您可能会在许多现有代码中看到这一点。

幸运的是，C++有一个包含各种时钟的计时库，我们可以使用它来生成种子值。如果程序连续快速运行，为了最大限度地减少两个时间值相同的机会，我们希望时间精度比较高。为此，询问计算机时钟自它可以测量的最早时间以来已经过了多少时间。这个时间是以“滴答”为单位测量的，这是一个非常小的时间单位（通常是纳秒，但可以是毫秒）。

 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


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

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

	// 创建一个均匀随机数分布器，可以将PRNGS的输出归一化到1 到 6 之间
	std::uniform_int_distribution die6{ 1, 6 }; // 对于 C++14, 可以写成 std::uniform_int_distribution<> die6{ 1, 6 };

	// 打印一堆随机数
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << die6(mt) << '\t'; // 产出一个投掷结果

		// 每输出10个数字，换行
		if (count % 10 == 0)
			std::cout << '\n';
	}

	return 0;
}

上述程序与之前的程序相比只有两个变化。首先，引入，它使我们能够访问时钟。其次，使用时钟的当前时间作为Mersenne Twister的种子值。

现在，该程序生成的结果在每次运行时都应该不同，您可以通过多次运行来进行实验验证。

这种方法的缺点是，如果程序快速连续运行几次，则每次运行生成的种子不会有太大差异，这可能会从统计角度影响随机结果的质量。对于普通程序，这并不重要，但对于需要高质量、独立结果的程序，这种播种方法可能不够。

提示

std::chrono::high_resolution_clock是一个流行的选择，而不是std::chrono::steady_clock。std::chrono::high_resolution_clock是使用最细粒度时间单位的时钟，但它使用当前系统时钟，用户可以更改或回滚该时间。std::chrono::steady_clock的滴答时间可能不太精细，但它是唯一一个保证用户无法调整的时钟。

使用随机设备播种

随机库包含一个名为std::random_device的类型，该类型是由实现定义的PRNG。通常，避免由具体实现定义的功能，因为它们不能保证质量或可移植性，但这是例外情况之一。通常，std::random_device将向操作系统请求随机数（它如何做到这一点取决于操作系统）。

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


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

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

	// 创建一个均匀随机数分布器，可以将PRNGS的输出归一化到1 到 6 之间
	std::uniform_int_distribution die6{ 1, 6 }; // 对于 C++14, 可以写成 std::uniform_int_distribution<> die6{ 1, 6 };

	// 打印一堆随机数
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << die6(mt) << '\t'; // 产出一个投掷结果

		// 每输出10个数字，换行
		if (count % 10 == 0)
			std::cout << '\n';
	}

	return 0;
}

在上面的程序中，使用从std::random_device的临时实例生成的一个随机数来播种Mersenne Twister。如果多次运行该程序，每次也应产生不同的结果。

std::random_device的一个潜在问题:它不需要是不确定性的，这意味着在某些系统上，它可能会在程序每次运行时产生相同的序列，这正是我们试图避免的。MinGW中存在一个错误（在GCC 9.2中修复），它存在这样的问题，使std::random_device变得无用。

当然，最流行的编译器（GCC/MinGW、Clang、Visual Studio）的最新版本支持std::random_device的正确实现。

最佳实践

使用std::random_device为PRNG设定种子。

Q: std::random_device{}()是什么意思？

std::random_device{}创建一个值初始化的临时对象，类型为std::random_device。然后，()在该临时对象上调用operator()，它返回一个随机值（我们将其用作Mersenne Twister的初始值设定项）

它相当于调用以下函数，该函数使用您更熟悉的语法:

1
2
3
4
5


unsigned int getRandomDeviceValue()
{
   std::random_device rd{}; // 创建一个 std::random_device 对象
   return rd(); // 返回rd对象上调用operator()的结果
}

使用std::random_device{}()允许在不创建命名函数或命名变量的情况下获得相同的结果，更简洁。

Q: 如果std::random_device本身是随机的，为什么不使用它来代替Mersenne Twister？

因为std::random_device是实现定义的，所以不能对它做太多假设。访问它可能很慢，或者它可能导致我们的程序在等待更多随机数可用时暂停。它保存的随机数池子也可能很快耗尽，这将影响通过相同方法请求随机数的其他应用程序。因此，std::random_device一般地用于播种其他PRNG，而不是作为PRNG本身。

仅为PRNG播种一次

许多PRNG可以在初始播种后重新播种。这本质上是重新初始化随机数生成器的状态，使其从新的种子状态开始生成结果。通常应避免重新播种，除非有特定的原因这样做，因为它可能会导致结果不那么随机，或者根本不是随机的。

下面是新程序员常见错误的一个例子:

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


#include <iostream>
#include <random>

int getCard()
{
    std::mt19937 mt{ std::random_device{}() }; // 每次函数调用，都生成一个PRNG，并重新播种
    std::uniform_int_distribution card{ 1, 52 };
    return card(mt);
}

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

    return 0;
}

在getCard()函数中，每次调用函数时都会创建随机数生成器并进行播种。这是低效的，并且可能会导致较差的随机结果。

最佳实践

只对给定的伪随机数生成器进行一次种子设定。

Mersenne Twister与播种不足的问题

Mersenne Twister的内部状态大小为624字节。在上面的示例中，从时钟或std::random_device中播种，种子只是一个32位整数。这意味着本质上是用4字节的值初始化624字节的对象，这大大低于Mersenne Twister的内部状态。随机库尽其所能用“随机”数据填充剩余的620个字节……但它不能神奇地工作。播种不足的PRNG可能生成对于需要最高质量结果的应用程序来说次优的结果。例如，使用单个32位值播种std::mt19937将永远不会生成数字42作为其第一个输出。

那么我们如何解决这个问题呢？截止C++20，没有简单的方法。但确实有一些建议。

首先，让我们讨论一下std::seed_seq（它代表“种子序列”）。在上一课中提到，理想情况下，希望种子数据的比特数与PRNG的状态相同，否则PRNG将不足。但在许多情况下（特别是当PRNG具有大型状态时），不会有那么多的随机种子数据。

seedseq是一种旨在帮助实现这一点的类型。可以尽可能多地传递给它随机值，然后它将根据需要，生成尽可能多的无偏种子值来初始化PRNG的状态。因此，如果您使用单个32位整数（例如，从std::random_device）初始化std::seed_seq，然后使用std::seed_seq对象初始化Mersenne Twister，则std:∶seed_seq将生成620字节的额外种子数据。结果不会令人惊讶地高质量，但总比什么都没有要好。

首先，给std::seed_seq使用的随机数据越多，效果越好。因此，最简单的想法是使用std::random_device来为std::seed_seq提供更多的数据。如果使用来自std::random_device的8个数字而不是1来初始化std:∶seed_seq，则由std::seed_seq生成的其余数字会更好:

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


#include <iostream>
#include <random>

int main()
{
	std::random_device rd{};
	std::seed_seq ss{ rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd() }; // 使用std::random_device产出的8个随机数作为种子
	std::mt19937 mt{ ss }; // 使用std::seed_seq初始化Mersenne Twister

	// 创建一个均匀随机数分布器，可以将PRNGS的输出归一化到1 到 6 之间
	std::uniform_int_distribution die6{ 1, 6 }; // 对于 C++14, 可以写成 std::uniform_int_distribution<> die6{ 1, 6 };

	// 打印一堆随机数
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << die6(mt) << '\t'; // 产出一个投掷结果

		// 每输出10个数字，换行
		if (count % 10 == 0)
			std::cout << '\n';
	}

	return 0;
}

这非常简单，没有太多的理由不这样做。

其次，可以对std::seed_seq使用其他“随机”输入。我们已经向您展示了如何从时钟中获取值，因此您可以轻松地输入该值。有时使用的其他内容包括当前线程id、特定函数的地址、用户的id、进程id等。这样做超出了本文的范围，读者可以自行实现。

另一种方法是使用具有较小状态的不同PRNG。许多好的PRNG使用64或128位状态，可以使用std::seed_seq轻松初始化。

Q: 为什么不从std::random_device中给定std:∶seed_seq 156个整数（624个字节）？

当然可以！然而，这可能很慢，并且有耗尽std::random_device使用的随机数池的风险。

预热PRNG

当PRNG被给予劣质种子（或种子不足）时，PRNG的初始结果可能不是高质量的。因此，一些PRNG受益于“预热”，这是丢弃从PRNG生成的前N个结果的技术。这允许混合PRNG的内部状态，以便后续结果具有更高的质量。通常会丢弃几百到几千个初始结果。PRNG的周期越长，应丢弃的初始结果越多。

使用seed_seq初始化的std::mt19937会执行预热，因此我们不需要显式预热std::mt19937对象。

旁白

Visual Studio的rand()实现有（或仍然有？）一个错误，其中第一个生成的结果将不会充分随机。您可能会看到使用rand()的旧程序丢弃单个结果，以避免此问题。

调试使用随机数的程序

使用随机数的程序可能很难调试，因为程序每次运行时可能会表现出不同的行为。有时它可能工作，有时它可能不工作。调试时，确保程序每次以相同的方式执行是有帮助的。这样，您可以根据需要多次运行程序，以隔离错误所在。

由于这个原因，在调试时，将导致错误行为发生的特定值（例如5）作为PRNG的种子是一种有用的技术。这将确保程序每次都生成相同的结果，从而使调试更容易。一旦发现错误，就可以使用正常的播种方法再次开始生成随机结果。

常见问题解答

Q: 救命啊！随机数生成器正在生成相同的随机数序列。

如果随机数生成器在每次运行程序时都生成相同的随机数序列，那么您可能没有正确地为其设定种子（或根本没有）。确保使用每次运行程序时都会更改的值对其进行播种。

Q: 救命啊！随机数生成器不断地生成相同的数字。

如果您的随机数生成器每次请求随机数时都会生成相同的数字，那么您可能是在生成随机数之前重新播种随机数生成器，或者是为每个随机数创建新的随机数生成器。

8.12 随机数生成简介

8.14 全局随机数