c - 如何使 OSX 的 rand() 无法通过光谱测试？

Question

出于编程类(class)的目的，我试图说明通常随标准 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;
}

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

我本以为会显示出更多结构，例如人们发现的 on Wikipedia .我在这里做错了什么吗？我应该在更多维度上绘图吗？

更新

根据 pjs 的建议，我放大了图中数字小于 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

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

Answer 1

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

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

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

附录

我已经从 Apple rand() 函数中提取了十亿个数字，但只打印了两个值都小于 200 万的数字，即绘图的左下角。果然，他们倒在了线上。由于线条的密度，您只需要真正放大才能看到它。

老乔治是个聪明人!