単体テストしたい疑似乱数ジェネレーター (PRNG) クラスがあります。次の 2 つの方法があります。
最初のアプローチは、ジェネレーターのホワイト ボックス テストを実行しないため、ユニット テストではないと思いますが、クラスの責任を適切にテストします。2 番目のアプローチは、アルゴリズムに焦点を当てた実際の単体テストに似ていますが、クラスがその責任を果たしているかどうかについての証拠はあまりありません。
どちらのアプローチを好みますか、またその理由は何ですか?
同じ PRNG アルゴリズムの別の実装を取得し、既知のシードに基づいて少数の長いテスト ケースを生成し、アルゴリズムの実装が他のすべての実装と一致することを確認します。テストするデータが多ければ多いほど、そうなる可能性が高くなります。真剣に取り組みたい場合は、アルゴリズムの FIPS 検証がどのように行われているかを調べてください。
出力がランダムであるかどうかをテストする必要はありません。これは、他の人が再現できるよりもはるかに多くの研究がアルゴリズムで行われているためです。
独自の PRNG アルゴリズムを発明した場合は、コードのテストとは別に、新しいアルゴリズムもテストする必要があるため、かなり異なる問題が発生します。やるべきことはいろいろありますが、最も重要なのは、出力に対する統計的テストと、他の暗号学者によるピア レビューだと思います。ただし、基本的には、テスト方法を知るための十分な知識がなくても PRNG アルゴリズムを設計した場合、それは無駄になります。
PRNG のテストには、PRNG のパフォーマンスを示す一連の統計テストであるENTを使用します。これがアプローチ1だと思います。
次の両方が当てはまることを確認したいので、最終的には両方のテストが必要になると思います。
(1) 数値が適切に分散されていること、および (2) 特定のアルゴリズムが期待どおりに機能していること。
おそらく、最初のテストはたまにしか実行できませんが、2 番目のテストは、コードの変更によってアルゴリズムが壊れていないことを確認するために使用できます。
あなたの最初のポイント（＃1）は、使用されているアルゴリズムによって決定される、生成された乱数の品質をテストする際により多くなると思います。2 番目のポイント (#2) は、アルゴリズムの実装をテストする際に役立ちます。アルゴリズムを設計した場合、両方のテストが重要です。実証済みのパフォーマンスのアルゴリズムを実装した場合は、#2 で十分です。ただし、特定のジェネレーターの構造に関するある程度の知識を使用して、結果として得られたいくつかのシードとシーケンスをテストすることになるでしょう。
疑似乱数ジェネレーターの「ランダム性」は、一般に、数値が繰り返される前の平均反復回数として表されます。さまざまな「ランダム性」とパフォーマンスを持つ多数のアルゴリズムがあります。 Random.orgには、彼らのアルゴリズムで行われたいくつかの分析についての良い説明があります。ページの半分くらいのところにある写真をチェックしてください。静止画像では、2つのアルゴリズムがどれほどランダムであるかを簡単に確認できます。
PRNGの1つの機能（機能を装ったバグではなく、真の機能）は、予測可能であるということです。与えられたシードに対して、同じ数列を生成する必要があります。これは非常に重要であり、確率的（別名、ランダム）メソッドを使用するプログラムのテストとデバッグに必要です。
数列は、特定の統計分布に近似している必要があります。大きなシーケンス（たとえば10 ^ 6の数値）を生成してPRNGをテストし、シーケンスに対していくつかの統計的検定、特にカイ2乗検定（分布が正規分布の場合）を実行します。サンプルのヒストグラムを作成し、期待どおりに表示されるかどうかを確認します。
シードの設定方法を制御する場合、生成されるシーケンスは毎回同じである必要があります。これは、ホワイトボックステストを実行するのに適しています。テストを行うときは、サンプルを収集する前に、ジェネレーターを100回程度実行して「ウォームアップ」することもお勧めします。
これは、Donald Knuth のボリューム 2、Seminumerical Algorithms で言及されている Kolmogorov-Smirnov テストの実装を含むCodeProjectの記事です。InSciTek Jeff が前述したように、アルゴリズムのテストとアルゴリズムの実装のテストという 2 つの問題があります。KS テストは、実装のバグを見つける可能性が高く、アルゴリズム自体の品質をテストするための良い出発点です。
注意してください: PRNG を「発明」した場合は、おそらくそれを間違っており、最適な分布とは言えないものを作成している可能性があります。ジェネレーターのランダム性に関する基本的なテストは、カイ 2 乗テストです。
学校に戻って、私はシミュレーション課題用の乱数ジェネレーターを開発していましたが、非ランダム性を特定する方法が必要でした。
2 つの乱数を取り、それらを (x,y) グラフ化するという素晴らしいアイデアが浮かびました。人間の脳が非ランダムなパターンを検出できるのは驚くべきことです。(「ランダム パターン」は矛盾した表現です。)
PRNG を微調整して、グラフに表示された縞模様とスターバーストを削除し、まったく新しい視点で (log(x), log(y)) をプロットし、プロセスを繰り返しました。
後で、私は統計を取ることを余儀なくされ、奇妙な数学を実行してランダム性を定量化できることを知りました。
特定の PNRG アルゴリズムを実装していない限り、数値がランダムであると判断する方法はありません。これがランダム性の性質です。ええ、平均して、数値ジェネレーターが無限に近づくにつれて均一になりますが、無限の反復回数をテストするつもりはありません。
既知のアルゴリズムを実装している場合は、最初の数千の数値が、与えられた一連のシードで提供される結果と一致することを確認してください。ただし、可能なシードの数は無限であるため、確認する方法はありません。
一連の数字がランダムであることを数学的に証明することさえできません...
XKCD
ディルバート
モッドダウンされます...
厳密には、乱数発生器が本当にランダムかどうかをテストする方法はありません:-) 最初のアプローチでは、この量がどれほど大きくても、一定量のサンプルのみに対して適切な分布を維持できるかどうかの知識が得られます。2番目のアプローチは、アルゴリズムのように動作するかどうかの知識をサポートできますが、これも固定量のサンプルに対してです。
あなたができる最善のこと - 両方を使用してください。
Random.org は次のテスト スーツを使用しています: http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
ソフトウェア (unix および mac os x) は、http://csrc.nist.gov/groups/ST/toolkit/rng/documents/sts-2.1.1.zip からダウンロードできます。
ドキュメントはこちら: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf