如何使OSX的rand()无法进行光谱测试？

Question

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

但是当我绘制得到的散点图时,我得到的是:

我会期望某些东西显示更多结构,就像在维基百科上找到的那样.我在这里做错了吗？我应该绘制更多尺寸吗？

UPDATE

按照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's Theorem"说k元组(长度为k的向量)将落在有限数量的超平面上.边界是m**(1/k),其中k是元组的大小,m是用于生成器模数的数字.因此,如果模数是(2**31 - 1)并且您正在查看3组,(2**31 - 1)则从正确方向观察时,3-d图将显示不超过立方根或大约1290个平面的点.

所有LCG都受Marsaglia定理的约束.一个"好的"在上限或接近上限执行,一个坏的下降远远超过上限.这就是光谱测试有效测量的结果,这就是你在维基百科链接中看到的内容 - 来自地狱的LCG RANDU产生的三元组只有15架飞机.

Apple的碳库生成器使用16807作为其乘数和(2**31 - 1)模数.正如LCG一样,它并不是那么糟糕.因此,你的情节没有表现出兰多的极端情况.但是,如果您想要质量合理的随机数,请不要使用LCG.

附录

我已经开始从Apple rand()函数中获取数十亿个数字,但只打印出两个值都小于200万的那些数字,即你的情节的左下角.果然,他们落在了线上.由于线条的密度,你只需要真正放大才能看到它.

老乔治是一个聪明的家伙!