梅森旋转算法类

• 下载源代码文件 - 58.3 Kb

引言

Mersenne Twister (MT) 是由 Makoto Matsumoto 和 Takuji Nishimura[1][2] 于1996-1997年期间开发的伪随机数生成器 (PRNG)。MT 具有以下优点：

• 它在设计时考虑了各种现有生成器的缺陷。
• 比任何其他实现的生成器都具有更长的周期和更高的均值分布性。（已被证明其周期为 2^19937-1，并保证了 623 维的均值分布特性。）
• 生成速度快。（虽然取决于系统，但据报告，在具有流水线和缓存内存的系统上，MT 有时比标准的 ANSI-C 库更快。）
• 内存使用高效。

功劳归于创作者

我提供了一个 C++ 类 (CRandomMT)，它封装了创作者的工作。我不会为此声称功劳，我只是提供一个面向对象 (OO) 版本的代码，您可以直接将其集成到您的游戏或应用程序中。

CRandomMT

灵感

2000年，我正在为一款 Roguelike 游戏开发一个随机地下城生成器，并在 rec.games.roguelike.development 上询问大家使用什么 PRNG。有人（或者一两个人）建议我试试 MT。在了解了它的优点（见上文）后，我决定下载它并将其集成到我的 Roguelike 游戏中。令我惊讶的是，我找不到该算法的面向对象 (OO) 版本，于是我立即着手“包装”代码。我的意思是，我们 C++ 程序员不就是这么做的吗？

汗水

包装代码并不难，实际上并没有流多少汗水，这让我更加好奇为什么这个算法没有被封装成 C++ 类并公开提供。尽管如此，我还是按照流程，把这个函数放这里，那个函数放那里，这个应该设为私有，你知道的，直到我拥有了一个完全封装好的版本，随时可用。

Roguelike 游戏通常需要大量的随机数，因此，我的下一个任务是添加几个方法，以使我的 Roguelike 游戏更容易编写，并且代码意图易于阅读。掷骰子的标准命名法是
<骰子数量>d<骰子面数>，所以，要掷 2 个 6 面骰子，您会写 2d6。经过一番思考，我确定标准命名法很难转化为我类的函数，但如果我反转命名法，使其读作
d<骰子面数><骰子数量>，我就可以轻松地创建描述代码意图的函数，例如 `CRandomMT::D6(int _DiceCount)` 和 `CRandomMT::D25(int _DiceCount)`。讽刺的是，这些只是 `CRandomMT::RollDice(int _DieSize, int _DiceCount)` 函数的包装器。

完成

啊，完成……这确实是最难的部分。我完成了我向您展示的类，甚至完成了这篇文章。但我未能完成 Roguelike 游戏。就像我刻录到 CD 的所有东西一样，我想我总有一天会抽出时间完成那项工作。我的意思是，我们 C++ 程序员不就是这么做的吗？

类描述

我应该首先指出，许多函数对于一般用途来说是不必要的，而且它们都是内联的。因为这是一个游戏，我需要大量的随机数，所以我选择了速度而非大小。

CRandomMT::CRandomMT()
这是默认的构造函数。

CRandomMT::CRandomMT(ULONG seed)
一个您提供种子值的构造函数。

CRandomMT::~CRandomMT()
析构函数。

CRandomMT::SeedMT()
用于为随机数生成器设置种子或重新设置种子。

ULONG CRandomMT::RandomMT()
返回一个无符号长随机数。

int CRandomMT::RandomRange(int hi, int lo)
返回一个落在指定范围内的整数随机数。

int RollDice(int face, int number_of_dice)
返回一个用于指定骰子数量和骰子面数的整数随机数。

int CRandomMT::D#(int die_count)
返回一个模拟指定骰子数量的掷骰结果（由 # 确定）。这些只是 `RollDice()` 的包装器。

int CRandomMT::HeadsOrTails()
返回 0 或 1，用于模拟硬币翻转。

示例用法

#include "Random.h"	
	.
	.
	.
	CRandomMT MTrand(GetTickCount());
	int rand_3d6 = MTrand.D6(3);		// roll 3 six sided die
	.
	.
	.

关于演示应用程序

演示应用程序是一个相当平庸的例子，但它确实展示了 MT 算法提供的均值分布性和速度的提升。尽管我没有从算法中感知到更好的分布，但速度的提升非常显著，因为随机例程被放在了内联中。在这里，我们模拟了 100,000 次硬币翻转，然后通过 `CProgressCtrl` 和几个用于文本显示的静态控件来直观地显示结果。

*
• 函数内百分比：在此行及其调用的函数上花费的时间占函数总时间的百分比。
• 调用次数：函数被调用的次数。
• 平均值：会话期间函数的平均执行时间。

更快？

在速度方面，很明显 MT 算法要快得多。区别在于，内联版本的 `FlipMersenne()` 平均为 26,168.42，而 `FlipRand()` 的平均为 41,507.23，速度提升了约 45%。这对于需要大量随机数的游戏来说可能很重要。即使是非内联版本中速度的较小提升，对于需要生成数十亿个随机数的应用程序来说，也能节省大量处理器资源。

均值分布性？

硬币正面或反面的概率使用数学公式表示为1/n。其中 n 是抛硬币的次数。在演示应用程序中，我们模拟了 100,000 次硬币翻转。令我惊讶的是，`rand()` 在 50/50 的假设下提供了非常好的结果。

我启动了应用程序并打开了 Excel，接下来我模拟了 100,000 次硬币翻转 10 次，然后计算了每次迭代结果的平均值。这是结果：

上面 `rand()` 的结果似乎比 MT 更接近期望的 50/50 的硬币翻转分布。当您将很小的误差百分比添加到这个统计样本中时，很明显这个测试更多的是不分胜负。这样一来，速度就成了决定是否使用 MT 算法的唯一因素。

结论

追求完美的 PRNG 是一个持续的努力，让计算机科学家和数学家都感到棘手。Mersenne Twister 通常被认为速度快、体积小且分布均匀。我喜欢在 PIII 900MHz 的机器上（使用未展开循环）大约 0.45 秒就能生成 1,000,000,000 个随机数。

谢谢

感谢 Makoto Matsumoto 和 Takuji Nishimura 创建了该算法。我还想感谢我的朋友和商业伙伴 Derek Licciardi 在统计分析方面的见解和专业知识。

链接

• Compuware Corporation TrueTime 的制造商

参考文献

• [1] "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator", M. Matsumoto 和 T. Nishimura, ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3--30。
• [2] Mersenne Twister: A random number generator, www.math.keio.ac.jp/~matumoto/emt.html

历史

• 2003年2月19日 - 更新了源代码下载