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() のスペクトル テスト

ウィキペディアで見つけたもののように、もっと構造を示すものを期待していたでしょう。ここで何か間違ったことをしていますか?より多くの次元でプロットする必要がありますか?

アップデート

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 によって特定された問題に悩まされています。「マルサグリアの定理」では、k-タプル (長さ k のベクトル) は有限数の超平面に収まると述べています。境界は ですm**(1/k)。ここで、k はタプルのサイズ、m はジェネレーターのモジュラスに使用される数値です。したがって、モジュラスがであり、3 のセットを見ている場合、3 次元プロットは、正しい方向から見たときに、(2**31 - 1)の立方根以下、または約 1290 平面に収まる点を示します。(2**31 - 1)

すべての LCG は、マルサリアの定理に従います。「良い」ものは上限またはそれに近いパフォーマンスを示し、悪いものは上限をはるかに下回ります。それがスペクトル テストが効果的に測定しているものであり、ウィキペディアのリンクで見たものです。地獄の LCG である RANDU は、わずか 15 平面に収まるトリプレットを生成します。

(2**31 - 1)Apple のカーボン ライブラリ ジェネレーターは、乗数および係数として16807 を使用します。LCGが行っているように、それはそれほど悪いことではありません。したがって、あなたのプロットはRANDUと同じ極端を示していません. ただし、まともな品質の乱数が必要な場合は、LCG を使用しないでください。

補遺

私は先に進んで、Apple rand() 関数から 10 億の数値をクランクアップしましたが、ペアの両方の値が 200 万未満のもの、つまりプロットの左下隅のみを出力しました。案の定、彼らは列に並んでいます。線が密集しているため、実際に拡大して見る必要があります。

オールド・ジョージは頭のいい奴だった!

仕事中のマルサリア

于 2013-04-29T23:30:22.473 に答える