Random Number Generator Library Concepts

Introduction

乱数は、以下に示すような様々に異なる問題領域において要求される。

Boost Random Number Generator Library は、計算やセキュリティの領域を要求する 場合においてもこの生成子が使われ得るように、よく吟味され決定された特徴を持つ 乱数生成子のフレームワークを提供する。

計算領域における乱数の一般的な概論は、以下を参照のこと。

"Numerical Recipes in C: The art of scientific computing", William H. Press, Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd ed., 1992, pp. 274-328
[訳注: 日本語版は、丹慶 勝市 他訳「ニューメリカルレシピ・イン・シー 日本語版 ―C言語による数値計算のレシピ」東京: 技術評論社、1993年 (ISBN: 4874085601)]

問題領域の要求に応じて、乱数生成子の様々なバリエーションが利用できる。

全てのバリエーションはいくつかの共通する特徴をもっている。これらの（STLにお ける）concept は、NumberGenerator や UniformRandomNumberGenerator と呼ばれ る。各 concept の定義は次節を参照のこと。

このライブラリの最終目標は以下のとおりである。

Number Generator

数生成子は、引数を取らない関数オブジェクト (std:20.3 [lib.function.object]) であり、全て operator() の呼出し毎に数値 を返す。

以下の表において、Xは、T型のオブジェクトを返す数生 成子クラスである。また、uはXの値である。

NumberGenerator の必須条件
式 返値型 事前/事後条件
X::result_type T std::numeric_limits<T>::is_specialized は真であり、 T は LessThanComparable である。
u.operator()() T -

注意: NumberGenerator の必須条件は、返される数値の特性にいかなる制 約を課すのもではない。

Uniform Random Number Generator

一定乱数生成子は、与えられた範囲で一様に生成される乱数列を提供する NumberGenerator である。この範囲は、コンパイル時に固定されているか、もしくは オブジェクトの実行時構築の後(のみ)でも与えることができる。

いくつかの(有限)集合 S の下限値は、S の(唯一の)メンバ l であり、S における全ての v に関して、 l <= v が成り立つ。同様に、いくつかの(有限)集 合 S の上限値は、S の(唯一の)メンバ u であり、S における全ての v に 関して、 v <= u が成り立つ。

以下の表において、Xは、T型のオブジェクトを返す数生 成子クラスであり、v は、X の定値である。

UniformRandomNumberGenerator の必須条件
式 返値型 事前/事後条件
X::has_fixed_range bool コンパイル時定数。 true であれば、乱数が一定に生成される範囲はコンパイル時に決定しており、 メンバ変数 min_value と max_value が存在する。
注意: このフラグは、コンパイラの制限により false になり得る。
X::min_value T コンパイル時定数。 min_value は v.min() と同値である。
X::max_value T コンパイル時定数。 max_value は v.max() と同値である。
v.min() T operator() によって返される全ての値集合の下限を返す。 この関数の返値はオブジェクトの生存期間を通じて不変である。
v.max() T std::numeric_limits<T>::is_integer が真であれば、operator()によって返される全ての値集合の上限、 偽であれば、operator()によって返される全ての値集合の上限より大きな、表現可能な最小の数を返す。 いかなる場合においても、この関数の返値はオブジェクトの生存期間を通じて不変である。

メンバ関数 min、max、および operator() は、償却定数時間計算量を持つ。

注意: 整数生成子 (i.e. 整数 T) においては、生成される 値 x は、min() <= x <= max() を満たす。非整 数生成子 (i.e. 非整数 T)においては、生成される値 x は、min() <= x < max()を満たす。
論拠: min と max による範囲の記述は2つの 目的に役立つ。一つは、[0..1) といったような正統な範囲に対する値のスケーリン グを可能にする。もう一つは、さらに進んだプロセスのために妥当であるかもしれな い値の意味のあるビット(significant bit) を記述する。
整数における範囲は、閉じられた間隔 [min, max] であるが、これは基礎となる型が 半開の間隔 [min, max+1) を表現することができない可能性があるためである。非整 数における範囲は、これまでの版のどちらつかずの状態より実用的であるため、半開 の間隔 [min, max)である。

注意: UniformRandomNumberGenerator コンセプトは operator()(long) を必須としていないため、RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]) の必須事項を満足していない。この要求 を満足するためには random_number_generator アダプタを使用すること。
論拠: 整数範囲を持つ生成子による出力の異なる整数範囲へのマッピング は些細なことではないので、operator()(long) は供給されていない。

Non-deterministic Uniform Random Number Generator

非決定論的一様乱数生成子は、確率過程に基づく UniformRandomGenerator である。 それゆえ、この生成子は一連の真に無作為な数を提供する。このような過程には、放 射性核種崩壊、ツェーナー・ダイオードのノイズ、量子粒のトンネリング、サイコロ を転がす、壺から引き当てる、コインを投げる、といった例を挙げることができる。 環境に依存するならば、ネットワーク・パケットの内部到達時間や、キーボードのイ ベントも確率過程の近似値になりえる。

random_device クラスは非決定論的乱数生成子のモデルである。

注意: このタイプの乱数生成子は、セキュリティ・アプリケーションに有 用である。外部からの攻撃者が数を予想し、暗号や認証鍵を入手されるのを防ぐ。そ こで、このコンセプトのモデルは、環境によって可能な範囲にかけて、いかなる情報 も漏れないよう注意深くなければならない。例えば、一時的な記憶域が必要でなく なったときにすぐに明示的に消去することは賢明である。

Pseudo-Random Number Generator

擬似乱数生成子は、決定論的擬似乱数列を提供する UniformRandomNumberGenerator である。 この擬似乱数は、いくつかのアルゴリズムと内部状態に基づいている。線 形合同生成子と逆合同生成子[?]は、このような擬似乱数生成子の例である。しばし ば、これらの生成子はパラメータに非常に敏感である。悪い実装が使われるのを避け るため、外部のテスト・スーツは生成された数列と提供された値の妥当性が実際に一 致することを確かめるべきである。

Donald E. Knuth は彼の著書 "The Art of Computer Programming, Vol. 2, 3rd edition, Addison-Wesley, 1997" の中で、擬似乱数生成に関して広範囲に及ぶ概観 を示している。特定の生成子に関する記述の中には補足の参考資料が含まれている。

注意: 擬似乱数生成子の状態は必然的に有限であるため、生成子によって 返される数列はいずれはループすることになる。

UniformRandomNumberGenerator の必須事項に加えて、擬似乱数生成子にはいくらか 追加の必須事項がある。下記の表において、X は T 型 のオブジェクトを返す擬似乱数生成子クラスであり、x は T の値、u は X の値、そして v は const な X の値である。

PseudoRandomNumberGenerator 必須事項
式 返値型 事前/事後条件
X() - 実装定義の状態で生成子を作成する。 注意: このように作成された生成子は、従属[?]しているか全く同一の乱数列を生成する可能性がある。
explicit X(...) - ユーザに提供された状態を用いて生成子を作成する。 実装はコンストラクタの仮引数を明示すること。
u.seed(...) void 現在の状態を引数に従って設定する。 少なくともデフォルトではないコンストラクタと同様のシグネチャを持つ関数を提供すること。
v.validation(x) bool あらかじめ計算されハードコーディングされた、生成子の乱数列における 10001 番目の要素と x とを比較する。 妥当性の検証が有意味であるために、生成子はデフォルトコンストラクタによって構築されていなければならず、また seed は呼ばれていてはならない。

注意: seed メンバ関数はSTLコンテナの assign メンバ関数と同様のものである。しかし、この名づけ方はふさ わしくなく思われる。

擬似乱数生成子のクラスは EqualityComparable でもあらねばならない。すなわち、 operator== を実装しなければならない。2つの擬似乱数生成子は、双 方とも状態を与えられてから全く同一の数列を返すならば、等値であると 定義される。

擬似乱数生成子のクラスは、また、operator<< と operator>> を実装した Streamable コンセプト[の要求]を満た すべきである。そうすれば、operator<< が今の擬似乱数生成子 の全ての状態を与えられた ostream に書き込み、 後で operator>> を用いて状態を復元することが可能である。状態 は、プラットフォーム非依存のマナーに則って書き込まれるべきであるが、その際書 き込んだものと読み込んだものが同じであるために locale が使われ ることが想定される。
状態を復元された擬似乱数生成子と、その状態を書き込ん だ時の擬似乱数生成子は等値であるべきである。

擬似乱数生成子のクラスは、CopyConstructible(コピーコンストラクト可能) で Assignable(代入可能) であるかもしれない。しかし、オリジナルの数列とコピーさ れたそれは強く相関されていることに注意すること。(実際、それらは全く同じもの である。) このことによっていくつかの問題領域において[CopyConstructive で Assignable な擬似乱数生成子が]不適切なものになるかもしれない。それ故、擬似乱 数生成子をコピーすることは阻止されている。 [コピーではなく、]常に(非 const な)参照で渡されるべきである。

rand48, minstd_rand, そして mt19937 といったクラスは、擬似乱数生成子のモデルである。

注意:この種の乱数生成子は数値計算,ゲームあるいはテストに有用であ る。非ゼロの引数を取るコンストラクタと seed() メンバ関数は、 ユーザの提供する状態が導入されることを許可している。このことは、モンテ･カル ロアルゴリズムをデバッグしたり特定のテストシナリオを解析したりするのに有用で ある。Streamable コンセプトのおかげで、生成子の状態を保存/復元することができ る。例えば、あるテスト・スーツを後で再動作させることができる。

Quasi-Random Number Generators

準乱数(quasi-random number)生成子は、決定論的数列を提供する数生成子である。 この準乱数は、いくつかのアルゴリズムと内部状態に基づいている。 この数は、いかなる(一様分布や連続した値の独立性といった)静的な特徴も持たない。

注意: 準乱数生成子は、特別に巧みに作られた乱数列が近似値をより早く 収束させるようなモンテ･カルロ積分に有用である。

[誰かモデルを持っていないかい?]