• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(UTC):
    が更新

    履歴 編集

    type-alias
    <random>

    std::minstd_rand0

    namespace std {
      using minstd_rand0 = linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>;
    }
    

    概要

    最小標準MINSTD乱数生成器。

    これは線形合同法に、より良いパラメータを設定したものである。

    minstd_rand0は、オリジナルのMINSTDパラメータであり、1988年にStephen K. ParkとKeith W. Millerによって考案された。

    1993年にStephen K. Park、Keith W. Miller、Paul K. Stockmeyerによって推奨された、パラメータ改良版であるminstd_randもまた定義されている。

    備考

    C言語標準ライブラリのrand()関数は、実装によっては問題のある線形合同法のパラメータが設定されていた。たとえば、実装によっては以下のような問題が発生していた。

    • 生成される値の最下位ビットは、01が交互に生成されていた。これにより、生成される値は偶数と奇数が交互になっていた。
    • 生成される値の最大値が非常に小さく、RAND_MAXの値が32767となっていた。

    MINSTDでは、このような問題は発生しない。

    ただし、「Visual Studioのrand()を使うと危ない場合」という記事で指摘されているように、次元が増えていくと標準偏差から離れていき、乱雑さが低くなっていくことに注意。2次元座標や3次元座標を乱数から作るような状況で問題になりえる。

    要件

    minstd_rand0型オブジェクトをデフォルト構築した場合、10000番目に生成される擬似乱数の値は1043618065であること。

    乱数列の周期

    231 - 2

    サイズ

    sizeof(uint_fast32_t)
    

    パフォーマンス

    整数に対して、乗算、加算、剰余算を一回ずつ行う

    次元

    次に生成される乱数は現在の乱数に相関関係があるため、2次元以上では一様分布しない。

    このトレードオフは、各出力の間(現在の状態と次の状態)の相関関係が、無視できるほどしかないということを意味する。たとえばN次元のランダムなベクトルを生成する場合、各次元の値に相関関係がほぼない状態にできる。minstd_rand0の場合は1次元のみであるため、2次元以上のランダムな値を生成することには不向きである。

    シード、および生成される値の型

    uint_fast32_t

    予測可能性

    生成された値がひとつわかれば、次の値を予測できる。

    生成された値をXnとして、linear_congruential_engineの計算式に当てはめればよい。

    #include <iostream>
    #include <random>
    
    int main()
    {
      std::random_device seed_gen;
      std::minstd_rand0 engine(seed_gen());
    
      for (int i = 0; i < 10; ++i) {
        std::uint32_t result = engine();
        std::cout << result << std::endl;
      }
    }
    

    出力例

    888393797
    1928232235
    123456768
    468696774
    416663422
    2065444334
    1997251430
    487897753
    1004970425
    579049320
    

    バージョン

    言語

    • C++11

    処理系

    参照