使用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{};

	// 创建一个均匀随机数分布器，可以将PRNG的输出归一化到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()
		) };

	// 创建一个均匀随机数分布器，可以将PRNG的输出归一化到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{}() };

	// 创建一个均匀随机数分布器，可以将PRNG的输出归一化到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具有大型状态时），不会有那么多的随机种子数据。

std::seed_seq是一种旨在帮助实现这一点的类型。可以尽可能多地向它传递随机值，然后它会根据需要生成尽可能多的无偏种子值，用来初始化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

	// 创建一个均匀随机数分布器，可以将PRNG的输出归一化到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 全局随机数

本节目录