11

出于编程课程的目的，我试图说明标准 C 库通常附带的随机数生成器的弱点，特别是rand()OSX 附带的“坏随机数生成器”（引用手册页）。

我写了一个简单的程序来测试我对光谱测试的理解：

#include <stdio.h>
#include <stdlib.h>

int main() {
  int i;
  int prev = rand();
  int new;

  for (i=0; i<100000; i++) {
    new = rand();
    printf("%d %d\n", prev, new);
    prev = new;
  }
  return 0;
}

但是当我绘制生成的散点图时，我得到的是：

OSX 的 rand() 的光谱测试

我会期待一些显示更多结构的东西，比如在 Wikipedia 上找到的东西。我在这里做错了吗？我应该绘制更多维度吗？

更新

按照 pjs 的建议，我放大了图中数字小于 1e7 的部分，这是我发现的：

OSX 的 rand() 的光谱测试仅限于小于 1e7 的数字

我发现 pjs 显示的行完全相同。它们似乎是垂直的，但这是不可能的，因为这意味着某些值被rand(). 当我sort -n得到数据时，这是我所看到的（样本）：

571 9596797
572 9613604
575 9664025
578 9714446
580 9748060
581 9764867
584 9815288
586 9848902
587 9865709
590 9916130
592 9949744
127774 13971
127775 30778
127780 114813
127781 131620
127782 148427
127783 165234
127785 198848
127787 232462
127788 249269

换句话说，这些点位于几乎但不完全垂直的线上。

4

2 回答 2

12

线性同余生成器都存在 George Marsaglia 发现的问题。“Marsaglia 定理”说 k 元组（长度为 k 的向量）将落在有限数量的超平面上。界限是m**(1/k)，其中 k 是元组的大小，m 是用于生成器模数的数字。因此，如果模数是并且您正在查看 3 组，则从正确方向查看时(2**31 - 1)，3-d 图将显示落在不超过 的立方根或大约 1290 个平面上的点。(2**31 - 1)

所有 LCG 都服从 Marsaglia 定理。一个“好”的人表现在或接近上限，一个差的人远远低于上限。这就是光谱测试有效测量的内容，这就是您在维基百科链接中看到的内容 - 来自地狱的 LCG RANDU 产生的三胞胎仅落入 15 个平面。

Apple 的碳库生成器使用 16807 作为其乘数和(2**31 - 1)模数。随着 LCG 的发展，情况并没有那么糟糕。因此，您的情节没有显示出与 RANDU 相同的极端情况。但是，如果您想要质量不错的随机数，请不要使用 LCG。

附录

我已经开始从 Apple rand() 函数中计算出十亿个数字，但只打印了这对的两个值都小于 200 万的数字，即图的左下角。果然，他们掉线了。由于线条的密度，您只需要真正放大即可看到它。

老乔治是个聪明人！

马萨利亚在工作

于 2013-04-29T23:30:22.473 回答
3

假设 badrand是一个线性同余生成器，即它的形式：

next = a * prev + b (mod RAND_MAX+1)

你可以只取一些项并解出 和 的a方程b。之后，您应该能够生成输出的函数，从而使结构变得显而易见。

于 2013-04-29T20:14:32.810 回答