C 中 rand() 的当前实现有多好?

计算科学 C 随机数生成
2021-12-08 21:13:06

有很多文献表明rand()用于模拟可能是有害的。其中一些如下:

一个常见的建议是使用在数字食谱定义的ran1//函数ran2ran3

但这些似乎是对该功能的相当古老的批评rand所以我的问题是,它当前的实现(GCC/clang)如何衡量成为一个好的 RNG,比如蒙特卡洛模拟?

这是 rand() 在 glibc 中使用的函数的当前实现:(rand 调用 random,它调用 random_r)

3个回答

但这些似乎是对 rand 函数的旧批评

这可能是一个挑剔,但我想指出我认为这个逻辑的缺陷。编译器通常对更改程序行为极为保守,即使该行为(愚蠢地)取决于实现细节。

对于您熟悉的大型编译器来说,这可能会也可能不会,但可以想象,出于兼容性原因,编译器会保留损坏的遗留 RNG。

我的macbook上的以下程序:

#include <cstdlib>
#include <iostream>
using namespace std;

int main() {
  srand(1);
  for (int i = 0; i < 20; ++i) {
    cout << (i > 0 ? ", " : "") << rand();
  }
  cout << endl;
  return 0;
}

产生输出

16807, 282475249, 1622650073, 984943658, 1144108930, 470211272, 101027544, 1457850878, 1458777923, 2007237709, 823564440, 1115438165, 1784484492, 74243042, 114807987, 1137522503, 1441282327, 16531729, 823378840, 143542612

您可以在 OEIS 中查找:https ://oeis.org/A096550 ,它是序列

16807nmod(2311).

在 SmallCrush RNG 测试下这是如何做到的(在 TestU01 库中):

========= Summary results of SmallCrush =========

 Version:          TestU01 1.2.3
 Generator:        ulcg_CreateLCG
 Number of statistics:  15
 Total CPU time:   00:00:08.05
 The following tests gave p-values outside [0.001, 0.9990]:
 (eps  means a value < 1.0e-300):
 (eps1 means a value < 1.0e-15):

       Test                          p-value
 ----------------------------------------------
  1  BirthdaySpacings                 eps
  2  Collision                        eps
  6  MaxOft                           eps
 ----------------------------------------------
 All other tests were passed

据我所知,根本没有充分的理由假设这rand()可能没问题。如果你假设不是这样,你通常最终会编写一些极其不可移植的代码,这些代码会在不同系统上的不同编译器下崩溃。

尽管问题是关于 C 的,但我仍然认为以下有关 C++11 的信息是相关的。在 C++11 中,<random>添加了旨在修复许多 Crand()实现缺陷以及提供附加功能的功能。所以,如果你可以选择使用 C++11,我会指出你的注意力<random>它的好处

在大多数情况下,<random>函数族将提供足够质量的随机数(与rand()您在问题中链接的材料中提到的相反。批评rand()仍然相关(因为 ANSI 标准没有改变);但是,肯定夸大了。

我的建议是首先评估对更高质量随机数的需求,然后逐步进行。很有可能,出于特定目的<random>,甚至rand()会提供足够体面的结果。否则(不太可能),您可能必须使用特殊库甚至硬件生成器。

与您的问题相关的相关指标数量有限,理想情况下您应该在尝试实施 MC 之前了解这些指标!

关于rand():我已经编写了(并行)MC 方法,这些方法可以轻松绘制PRN,此时您循环由 提供的 PRN 序列,其周期为 if我理解您正确链接到的代码中的注释。现在您要么必须分析潜在的相关性是否会影响您的问题,要么您可以选择一个更长周期的 PRNG,从而避免问题(或至少将其推到更大的问题规模)。>109rand()23214.3109

尤其是在并行环境(运行 MC 模拟的常用方法)中,使用 MC 会rand()带来额外的问题,即多个进程可能最终将 PRNG 初始化为从同一位置开始,或者从它们的序列最终重叠的位置开始。后者将导致两个过程使用相同的 PRN 进行(据称)独立模拟。其他 PRNG,如 C++11 中使用的 Mersenne Twister 引擎也遇到了同样的问题,但程度较轻,因为它们的(有限的)参数集产生不同的序列,所以只要你不使用相同的种子初始化它们,它们就会产生不重叠的序列。

我使用的 AC 代码用于rand()并行 MC 方法,用于近似(非常大)矩阵的逆矩阵。我凭经验确定用 TRNG ( https://www.numbercrunch.de/trng/ ) 替换它 - 但是必须为它编写一个 C 包装器 - 可测量地减少最终结果的错误。特别是对于大型矩阵(例如,需要大量 PRN 的矩阵)。 注意这里:仅仅因为你被限制使用 C 并不意味着你不能使用 C++ 库,你只需要为你需要的函数编写包装器。