2013-03-22

極端な一様乱数ジェネレーターを作る

C++11の乱数ジェネレーターは、自前で実装できる。要件さえ満たしていればいいのだ。

一様乱数ジェネレーター(Uniform random number generator)は、ディストリビューションで使う最低限の要求であり、これさえ満たしていれば、ディストリビューションで使える。より広いエンジンの要求は、初期化方法とかのディストリビューションからの利用には必要ない要件を定義している。

ジェネレーターに必要な要件は以下の通り

Gをジェネレーターの型、gをGの値とする。TをGのresult_typeの型とする。

  • 式G::result_typeの結果はT、Tは符号なし整数型(コンパイル時)
  • g()はG::min()とG::max()の間の値を返す(償却定数時間)
  • G::min()はGのoperator()が返す最低値(コンパイル時)
  • G::max()はGのoperator()が返す最大値(コンパイル時)

G::min() < G::max()が成り立つこと。

つまり、以下のような極端なジェネレーターも規格の要件を満たしている。

// 0か1しか返さないジェネレーター
class binary_generator
{
private :
    std::mt19937 engine ;

public :
    using result_type = unsigned int ;
    static constexpr result_type min() { return 0u ; }
    static constexpr result_type max() { return 1u ; }

    result_type operator () ()
    {
        std::uniform_int_distribution< result_type > dist( min(), max() ) ;
        return dist( engine ) ;
    }

} ;

これは正しいジェネレーターである。実際に使ってみる。

int main()
{
    binary_generator gen ;
    std::uniform_int_distribution< int > dist( 1, 100 ) ;

    for ( int i = 0 ; i != 10 ; ++i )
    {
        std::cout << dist(gen) << std::endl ;
    }
}

ちゃんと動いているようだ。ちなみに、まともなuniform_int_distributionの実装ならば、一回のdist(gen)の実行につき、最低でも7回はジェネレーターのoperator ()を呼び出すはずだ。というのも、呼び出し一回に付き1bitの乱数しか得られないので、1から100までの100種類の乱数を正しく生成するためには、最低でも7bitの乱数が必要になるからだ。

C++11の標準ライブラリのディストリビューションは、このような極端なジェネレーターにもちゃんと対応している。読者は標準で用意されているディストリビューションを正しく使い、間違っても安直な剰余を使ってはならない。

// このようなコードを書くものは、海賊船に乗れず溺れ死ぬべきだ。
// また、彼らはただ死んで終わるものではない。
// 唯一神空飛ぶスパゲティモンスターが地獄のビール休火山に投げ込む者達だ。
// 彼らの支持者も同様だ。
// 理由は経験科学に基づかない者らには経験科学に基づかない死がふさわしいからだ。
// 詳しい理由はN3551などで熟知すべし。
int main()
{
    std::default_random_engine engine ;
    // 6面ダイスのつもり。
    // 明らかに、海賊服も眼帯も身につけたことがないカナヅチの書いた祝福されぬコードである。
    std::cout << 1 + engine() % 6 << std::endl ;
}

以下のように書くこと。

int main()
{
    std::default_random_engine engine ;

    // 1から6まで一様に分布する乱数
    std::uniform_int_distribution< int > dist( 1, 6 ) ;
    // 6面ダイス
    std::cout << dist(engine) << std::endl ;
}

No comments:

Post a Comment

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.