65.9K
CodeProject 正在变化。 阅读更多。
Home

简单随机数生成

John D. Cook
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.90/5 (101投票s)

2008 年 4 月 11 日

BSD

4分钟阅读

viewsIcon

727090

downloadIcon

17680

C# 中的一个简单随机数生成器

引言

随机数生成是一个棘手的业务。好的随机数生成算法很难发明。实现这些算法的代码很难测试。而使用随机数生成器的代码也很难测试。本文将介绍 SimpleRNG，一个非常简单的随机数生成器。该生成器使用了一个经过充分测试的算法，并且非常高效。因为它非常简单，所以很容易集成到项目中，也容易进行调试。

SimpleRNG 可用于生成具有多种统计分布的随机无符号整数和 double 值。

  • 贝塔
  • 柯西分布
  • 卡方分布
  • 指数
  • 逆伽马分布
  • 拉普拉斯分布（双指数分布）
  • 正常
  • 学生 t 分布
  • 均匀分布
  • 威布尔分布

为什么不直接使用 .NET 随机数生成器？

对于许多应用程序来说，使用哪种随机数生成器几乎无关紧要，而 .NET 运行时自带的生成器最为方便。然而，有时拥有自己的随机数生成器会很有帮助。以下是一些例子。

  1. 在调试时，能够完全访问随机数生成器会很方便。您可能希望检查生成器的内部状态，而当状态很小时会很有帮助。此外，暂时更改生成器，使其输出具有可预测性，有助于调试使用生成器的代码。
  2. 有时需要比较用不同语言编写的程序的输出。例如，在我工作的地方，我们经常将用 R 编写的原型代码用 C++ 重写，以使其更有效率。如果两个程序都使用各自库的随机数生成器，那么它们的输出就不能直接比较。但是，如果两个程序都使用相同的算法，例如这里使用的算法，那么结果可能会直接可比。（由于其他差异，结果可能仍然不匹配。）
  3. 内置生成器的统计质量可能不足以满足某些任务的需求。此外，在应用服务包时，生成器的属性可能会在未通知的情况下发生更改。

背景

George Marsaglia 是随机数生成领域的顶尖专家之一。他提出了一些简单的算法，但这些算法却能产生高质量的输出。本文介绍的生成器 SimpleRNG 使用了 Marsaglia 的 MWC（带进位乘法）算法。该算法有些神秘但非常简洁。该算法通过了 Marsaglia 的 DIEHARD 测试套件，这是随机数生成器的“试金石”。

SimpleRNG 的核心是三行代码。这是生成均匀分布无符号整数的方法。

private static uint GetUint()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;
}

这里 m_w 和 m_z 是无符号整数，是该类的唯一成员变量。这段代码为什么能产生高质量的随机数并不明显，但它确实可以。

然后，无符号整数被转换为开区间 (0, 1) 中的 double 值。（“开区间”意味着不包括端点；该方法不会返回 0 或 1，只会返回介于它们之间的数字。）

public static double GetUniform()
{
    // 0 <= u < 2^32
    uint u = GetUint();
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (u + 1.0) * 2.328306435454494e-10;
}

Using the Code

SimpleRNG 类有两个种子。它们有默认值，或者可以通过调用带有一个或两个参数的 SetSeed() 来指定。这些参数必须非零；如果参数为零，则会被替换为默认值。有些人可能更喜欢在这种情况下抛出异常，而不是静默修复问题。还有一个选项可以通过 SetSeedFromSystemTime() 从系统时钟设置种子值。一旦类被初始化，只有一个 public 方法可供调用：GetUniform()。

关注点

用于测试 SimpleRNG 的代码比 SimpleRNG 本身更复杂。作为演示包含的测试代码使用统计测试，即 Kolmogorov-Smirnov test，来确认生成器的输出具有预期的统计特性。如果此测试重复使用理想的随机输入，则平均而言，测试将在每次应用时失败一次。这在软件测试中非常罕见：测试**应该**偶尔失败！这就是统计学。如果测试失败，请不要惊慌。尝试使用另一个种子，它很可能会通过。该测试足以捕获大多数编码错误，因为错误很可能导致测试失败的频率远高于此。测试代码还使用了 RunningStat，这是一个在值累积时精确计算样本均值和方差的类。

延伸阅读

有关随机数生成的更多信息，特别是关于可能出错的微妙之处，请参阅 CodeProject 文章 随机数生成中的陷阱。如果您正在使用 C++，请参阅 使用 C++ TR1 进行随机数生成。

历史

  • 2008 年 4 月 11 日：首次发布
  • 2008 年 4 月 13 日：修订文章，解释为什么此生成器可能优于内置生成器
  • 2008 年 9 月 30 日：添加了“进一步阅读”部分
  • 2008 年 10 月 4 日：根据读者反馈修复了两个错误。现在种子不能为 0，并且 GetUniform 不能返回 0。
  • 2008 年 10 月 22 日：添加了生成正态（高斯）和指数随机样本的方法
  • 2010 年 2 月 19 日：修复了与 Marsaglia 的 MWC 算法不兼容的问题
  • 2010 年 4 月 30 日：添加了新分布的方法，扩展了测试代码
  • 2010 年 7 月 27 日：更新了文章
  • 2011 年 1 月 6 日：更新了文章和下载文件
  • 2011 年 3 月 16 日：根据 Craig McQueen 关于核心生成器低位数的评论，更新了文章和下载文件
© . All rights reserved.