libc的随机数生成器有缺陷？(libc random number generator flawe

考虑的算法来测试一定数目的从一组N个唯一号码的尝试的特定数目后捞起（例如，在N = 2的概率，什么在轮盘（不含0），它需要X试图用于概率黑色赢？）。

造成这种情况的正确分布是POW（1-1 / N，X-1）*（1 / N）。

然而，当我测试此用下面的代码，总有在X = 31一个深沟，独立地选自N，和独立地从种子。

这是一个无法在由于使用可以防止对PRNG的实现细节的内在缺陷，这是一个真正的bug，还是我忽视的东西明显？

// C

#include <sys/times.h>
#include <math.h>
#include <stdio.h>

int array[101];
void main(){

    int nsamples=10000000;
    double breakVal,diffVal;
    int i,cnt;

    // seed, but doesn't change anything
    struct tms time;
    srandom(times(&time));

    // sample
    for(i=0;i<nsamples;i++){
        cnt=1;
        do{
            if((random()%36)==0) // break if 0 is chosen
                break;
            cnt++;
        }while(cnt<100);
        array[cnt]++;
    }

    // show distribution
    for(i=1;i<100;i++){
        breakVal=array[i]/(double)nsamples; // normalize
        diffVal=breakVal-pow(1-1/36.,i-1)*1/36.; // difference to expected value
        printf("%d %.12g %.12g\n",i,breakVal,diffVal);
    }
}

经测试上了最新的Xubuntu 12.10与libc6的软件包2.15-0ubuntu20和Intel Core i5-2500 SandyBridge的，但我在几年前就已经发现了这个旧的Ubuntu的机器上。

我也使用Unity3D /单声道（不知道哪个版本的单，虽然）测试了在Windows 7上，这里的沟使用System.Random时，而统一的内置Unity.Random是不可见的沟（至少不是在X = 55发生为X <100）。

分布：

不同之处：

Answer 1:

这是由于glibc的的random()不是功能足够随机的。 根据这个页面 ，通过返回的随机数random()我们有：

oi = (oi-3 + oi-31) % 2^31

要么：

o i = (o i-3 + o i-31 + 1) % 2^31 。

现在取x i = o i % 36 ，并假设上述第一方程式是所使用的（在此情况与50％的几率为每个数）。 现在，如果x i-31 =0和x i-3 !=0 ，那么这样的机会x i =0小于1/36。 这是因为50％的时间o i-31 + o i-3将小于2 ^ 31，并且当发生这种情况，

x i = o i % 36 = (o i-3 + o i-31 ) % 36 = o i-3 % 36 = x i-3 ，

这是非零。 这会导致你看到31个样本的抽样0后的水沟里。

Answer 2:

什么在此实验的被测量是伯努利试验，其中成功定义为成功的试验之间的间隔random() mod k == 0对于一些k （在OP 36）。 不幸的是，它是由一个事实，即实施毁损random()是指伯努利试验在统计上不独立。

我们将编写rnd i为i th随机的（）”的`输出我们注意到：

rnd i = rnd i-31 + rnd i-3的概率0.75

_{rnd i = rnd i-31 + rnd i-3 + 1} RND I-3 + 1与概率0.25

（请参阅下面的一个证明纲要。）

让我们假设rnd i-31 mod k == 0 ，我们目前正在观察rnd i 。 然后，它必须是的情况下rnd i-3 mod k ≠ 0否则我们将有计数的周期为长度k-3

但（大部分时间） (mod k): rnd i = rnd i-31 + rnd i-3 = rnd i-3 ≠ 0

所以，目前的审判是没有统计学独立于以前的试验中，和成功后的31 ^次试验是不太可能会比在公正的系列伯努利试验的成功。

在使用线性同余发生器，通常建议实际上不适用于random()算法，是使用高阶比特，而不是低阶位，因为高阶位是“更随机”（也就是说，少用连续值相关）。 但是，这不会在这种情况下工作，要么，因为上面的身份持有同样出色的功能high log k bits作为函数mod k == low log k bits 。

事实上，我们可以期待一个线性同余发生器更好的工作，特别是如果我们使用输出的高阶位，因为虽然LCG是不是在蒙地卡罗模拟特别好，它不从的线性反馈受苦random()

---

random算法，默认情况下：

让state是无符号多头的载体。 初始化state 0 ...state 30使用种子，一些固定值，和混合算法。 为简单起见，我们可以认为状态向量是无限的，虽然只使用最后31个值，所以它是一个环形缓冲区实际执行。

为了产生rnd i : (Note: ⊕ is addition mod 2 32 .)

statei = statei-31 ⊕ statei-3

rndi = (statei - (statei mod 2)) / 2

现在，请注意：

(i + j) mod 2 = i mod 2 + j mod 2如果i mod 2 == 0或j mod 2 == 0

(i + j) mod 2 = i mod 2 + j mod 2 - 2如果i mod 2 == 1和j mod 2 == 1

如果i和j均匀地分布，第一壳体将发生的75％的时间，和第二壳体25％。

这样，由生成公式中替换：

rndi = (statei-31 ⊕ statei-3 - ((statei-31 + statei-3) mod 2)) / 2

= ((state i-31 - (state i-31 mod 2)) ⊕ (state i-3 - (state i-3 mod 2))) / 2或

     = ((statei-31 - (statei-31 mod 2)) ⊕ (statei-3 - (statei-3 mod 2)) + 2) / 2

这两种情况可以进一步简化为：

rndi = rndi-31 ⊕ rndi-3

_{RND I = RND I-31⊕} RND I-3 + 1

如上所述，第一种情况发生的时间的75％，假定RND _I-31和RND _I-3独立地从均匀分布中抽取（它们不是，但它是一个合理的第一近似值）。

Answer 3:

正如其他人所指出的， random()是不够随机的。

使用较高位，而不是低级的不能在这种情况下帮助。 根据手册（ man 3 rand ）， 旧的实现rand()曾在较低位的问题。 这就是为什么random()建议来代替。 虽然，目前执行的rand()使用相同的发电机作为random()

我想推荐的正确使用旧的rand()

if ((int)(rand()/(RAND_MAX+1.0)*36)==0)

...并得到了相同的深沟里，在X = 31

Interstingly，如果我混rand()与其它顺序的号，我摆脱了沟：

unsigned x=0;
//...

        x = (179*x + 79) % 997;
        if(((rand()+x)%36)==0)

我使用的是旧线性同余发生器 。 我选择了79，179和997随机从素数表。 这应该产生长度997的重复序列。

这就是说，这一招可能出台一些非随机性，一些足迹......把所得的混合序列必定失败其他统计检验。 x从来没有发生在连续迭代相同的值。 事实上，这恰恰是997反复重复的每一个值。

“” [..]的随机数不应该与随机选择的方法生成的。 有些理论应该被使用。”（DEKnuth，‘计算机程序设计艺术’，下册）

对于模拟，如果您希望确保，使用梅森倍捻机

文章来源: libc random number generator flawed?