TestU01
TestU01は乱数生成器(random number generator)の乱雑さ(randomness)の経験的な検定のためのユーティリティを集めたソフトウェア・ライブラリである。ANSI Cによって実装されている。[1]2007年モントリオール大学のPierre L’EcuyerとRichard Simardによって発表された。[2]
TesTU01では既存の論文で提示されていたり、広く使われているソフトウェアで用いられたりしている数種の疑似乱数が実装されている。 また一般の疑似乱数に対する良く知られた基本的な統計的な検定法の他いくつか論文で既に提案されていたものや独自の統計的な検定法が実装されている。これらの検定はTestU01で定義されている乱数生成器の他、ユーザによって定義されたものや、ファイルに格納されている乱数列に適用することができる。またより具体的には[0,1]区間の一様乱数、及びランダムなビット列双方に対するテスト・スイート(テストを集めたもの)が含まれている。乱数生成器により生成された数を成分とするベクトルをプロットする簡単なツールも提供されている。
歴史
編集乱数生成器の検定を様々な方法で行なうテストは初め1969年にドナルド・クヌースのThe Art of Computer Programming第一版で提案された。その後1996年発表されたen:George Marsagliaによる(15個のテストにより成る)en:Diehard testsが用いられるようになる。Diehard testにはテストに使われるパラメータが変えられない、新しいテストを加えられないという問題があり、それを動機として、TestU01ライブラリは開発された。
仕様
編集
TestU01には乱数生成器を調べるための4種の機能
(一)予めプログラムされている乱数生成器の実装
(二)特定の統計的検定の実装
(三)複数の統計的検定をまとめて行なう機能(batteries of statistical tests)の実装
(四)検定を数種類の乱数生成器(entire families of RNGs)にまとめて行なえる機能の実装
が用意されている。ある特定の検定がサイズが乱数生成器によって生成された(乱数の)個数nのサンプルに適用されたとしよう。テストのp-値はnが十分小さい場合はまともな値を示す。サンプルの個数nがある値n0を超えるとp-値は0か1に指数的に近づく。上記4番目の機能はある特定のテストと与えられた一連の乱数生成器の出力の関連の研究に用いられる。これにより、乱数生成器の周期に応じて、どれくらい以上の個数の乱数を生成させると検定を通らなくなってしまうかが分るのである。
TESTU01には(10個のテストから成る)"Small Crush", (96個のテストからなる)"Crush"そして(106個のテストよりなる)"Big Crush"など数種のテスト・スイートが含まれる。各スイートに含まれる特定の検定についてはユーザーガイドにてその詳細が説明されている。[3]1.7 GHz Pentium 4上のRed Hat Linux 9.0環境で、簡単な乱数生成器については、Small Crushはおよそ2分Crushはおよそ1.7時間Big Crushはおよそ12時間を要する。複雑な乱数生成器の場合、かかる時間は一律に2倍ないしそれ以上になる。なおDiehard testにかかる時間は同環境でおよそ15秒である。
関連
編集参考文献
編集- ^ The TestU01 web site.
- ^ Pierre L’Ecuyer & Richard Simard (2007),"TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators", en:ACM Transactions on Mathematical Software, 33: 22.
- ^ TestU01 User's Guide.