7

私はPRNG（Mersenne Twisterやrand()stdlibの機能など）をいじっています.PRNGによって生成されたランダムデータの品質を確認するのに役立つ良いテストが必要です. PRNG によって生成された乱数を使用して Pi の値を計算しましたがrand()、Mersenne Twister が区別を提供するのに非常に近いことがわかりました (小数点以下 10 桁まで精査する必要がありますか?)。

モンテカルロ シミュレーションについてはよくわかりません。品質の観点からそれらを区別するのに役立ついくつかのアルゴリズム/アプリケーション (単純でありながら適切な推論を提供できるもの) について教えてください。

EDIT 1:以前は気が付きませんでしたが、同様のスレッドがあります: How to test random numbers?

編集 2:コメントの 1 つに記載されているように、NIST の結果を解釈できません。random.orgからパターン (存在する場合) を視覚的に解釈するというこのアイデアを得て、その単純さのためにそれに従っています。誰かが私のテストのプロセスについてコメントしてくれたらとてもうれしいです:

  1. rand() と MT1997 を使用して、[0,1] から N 個のランダムを生成します
  2. もしそうなら(round(genrand_real1() / rand_0_1()))赤のピクセル、そうでなければ黒のピクセル

これが非常に正確な解決策ではないことは理解していますが、これが合理的な見積もりを提供する場合、現時点ではこれを受け入れることができます.

4

3 に答える 3

11

いくつかの統計テスト スイートが利用可能です。私は 120 個の PRNG を書き、コピーし、その他の方法で集め、テスト スイートごとに PRNG ごとに 4 時間を与えられたさまざまなテスト スイートでそれぞれをテストしました。

  • PractRand (標準、1 テラバイト) は、78 個の PRNG でバイアスを検出しました
  • TestU01 (BigCrush) が 50 個の PRNG でバイアスを発見
  • RaBiGeTe (拡張、512 メガビット、x1) は、40 個の PRNG でバイアスを検出しました
  • Dieharder (カスタム コマンド ライン オプション) が 25 の PRNG でバイアスを発見
  • Dieharder (-a コマンド ライン オプション) は、13 個の PRNG でバイアスを検出しました
  • NIST STS (デフォルト、64 メガビット x128) は、11 個の PRNG でバイアスを検出しました

PRNG に含まれていて、他のテスト スイートがすべて見逃したものはいくつありますか?

  • PractRand (標準、1 テラバイト) は、さまざまなカテゴリで 22 の固有のバイアスを検出しました。
  • RaBiGeTe (拡張、512 メガビット、x1) は、すべて LCG および組み合わせ LCG で、5 つの固有のバイアスを検出しました。
  • TestU01 BigCrush は、小さな混沌とした PRNG で 2 つの固有のバイアスを発見しました。
    他のテスト スイートでは、固有のバイアスは見つかりませんでした。

つまり、PractRand、TestU01、および場合によっては RaBiGeTe だけを使用する価値があります。

完全な開示: 私は PractRand を書いたので、PRNG のセットまたはその他の非定性的尺度のいずれかが有利にバイアスされる可能性があります。

その他の利点:

  • 私の意見では、PractRand と TestU01 が出力を解釈するのが最も簡単な傾向があります。
  • PractRand と Dieharder は、コマンド ライン インターフェイスを介してテストを自動化するのが最も簡単な傾向があると思います。
  • マルチスレッド テストをサポートしていたのは、PractRand と RaBiGeTe だけでした。

その他の欠点:

  • PractRand は、他のテスト スイートよりもテストに多くの入力を必要としました。RNG が非常に遅い場合や、生成されるデータ量が限られている場合は、問題になる可能性があります。
  • RaBiGeTe と NIST STS の両方にインターフェースの問題があります。
  • Dieharder と NIST STS の両方に誤検知の問題があります。
  • 私の意見では、NIST STS のインターフェイスは最悪でした。
  • Dieharder を Windows でコンパイルできませんでした。Windows で TestU01 をコンパイルすることはできましたが、少し手間がかかりました。
  • RaBiGeTe の最近のバージョンは、ソースがクローズドで Windows 専用です。

テストされた PRNG のセット: PRNG セットには、1 つの大きな GFSR、1 つの大きな LFSR、4 つの xorshift タイプの PRNG、2 つの xorwow タイプの PRNG、3 つの他の完全ではない LFSR PRNG が含まれています。これには、10 の単純な 2 のべき乗モジュラス LCG (許容される品質レベルに到達するために下位ビットを破棄する)、10 の 2 のべき乗モジュラスである非かなりの LCG、および主に LCG と非かなりの LCG に基づく 9 つの組み合わせジェネレーターが含まれます。 . これには、CSPRNG の強度を下げた 19 のバージョンと、完全な強度の CSPRNG が 1 つ含まれています。それらのうち、14 は間接/動的 s-box (RC4、ISAAC など) に基づいており、4 つは ChaCha/Salsa のパラメーター化であり、残りの 2 は Trivium バリアントでした。これには、LFSR/GFSR を数えずに、LFib タイプまたは類似のものとして広く分類可能な 11 の PRNG が含まれます。残り (約 35) は小さな状態カオス PRNG で、そのうち 10 は乗算を使用し、残りは算術およびビット単位の論理に限定されていました。

編集: gjrandにはテスト セットもあります。これは非常にあいまいで少し奇妙ですが、実際には非常にうまく機能します。

また、テストされたすべての PRNG は、非推奨の PRNG として PractRand に含まれています。

于 2014-11-26T23:13:44.387 に答える
4

乱数をテストするための 2 つの標準テスト スイートがあります。

  1. NISTテスト スイート。それらはC で実装されています。
  2. ダイハード テスト スイート(George Marsaglia が開発)。これらのテストのC ライブラリ実装があります。

RDieHarder と呼ばれるDieharderライブラリへの R インターフェイスがあります。このライブラリは、NIST と Diehard テスト スイートの両方へのインターフェイスを提供します。

于 2012-03-20T10:34:35.193 に答える
0

Knuthのシリーズの第2巻を調べるのが最善です。

短い読み物については、数値レシピの対応する章を調べてください。

MCシミュレーションのベースラインのようなものだけに関心がある場合は、線形合同法を避けるのが最善です。ほとんどの場合、メルセンヌツイスターで十分です。

于 2012-03-20T10:27:36.667 に答える