【本家Stack Overflowより】C++11の<random>で１個目に同じ乱数が出続けるという話

generates same number in Linux, but not in Windows
http://stackoverflow.com/questions/32730906/random-generates-same-number-in-linux-but-not-in-windows の記事が面白かったので紹介。

以下のコードにおいて、Linux環境では何度か実行しても、1回目に出る乱数が同じだったが、なぜか、という疑問。

# include <iostream>
# include <random>
# include <time.h>

using namespace std;

int main()
{
    const int upper_bound = 100;
    const int lower_bound = 1;

    time_t system_time = time(0);    

    default_random_engine e(system_time);
    uniform_int_distribution<int> u(lower_bound, upper_bound);

    cout << '#' << '\t' << "system time" << endl
         << "-------------------" << endl;

    for (int counter = 1; counter <= 5; counter++)
    {
        int secret = u(e);
        cout << secret << '\t' << system_time << endl;
    }   

    system("pause");
    return 0;
}

1回の実行で5個の乱数を出すこのコードを、質問者はWindows, Linux で各5回ずつ実行したが、Linuxでは、1個目の乱数が5回とも25になり、Windowsではその現象が起こらなかった、とのこと。2個目以降はWindows, Linuxともバラバラであった。

      | Windows:       | Linux:        
---------------------------------------
Run 1 | 54,01,91,73,68 | 25,38,40,42,21
Run 2 | 46,24,16,93,82 | 25,78,66,80,81
Run 3 | 86,36,33,63,05 | 25,17,93,17,40
Run 4 | 75,79,66,23,84 | 25,70,95,01,54
Run 5 | 64,36,32,44,85 | 25,09,22,38,13

私も試しにLinux環境で実行してみたところ、何度実行しても18が得られた。

で、それに対する回答が

• GCC標準ライブラリのlibstdc++では、default_random_engineはminstd_rand0、すなわち単純な線形合同法となっている。
• 乱数の生成方法は、 $x_{i+1} = (16807x_i + 0)\ mod\ 2147483647$だ。[1, 2147483646]までの乱数を生成することができる。
• この式から、仮に乱数の種を1変えれば、1個目に得られる乱数は大抵の場合16807だけ変わることがわかる。
• 一方、件のコードでは、uniform_int_distribution でこれを[1, 100]に割り当てている。もし乱数nが2147483600未満ならば(n-1)/21474836 + 1 を返し、それ以外なら新しい乱数でやり直す。
• ということは、たとえnが16807違っていたとしても、ほとんどの場合、同じ数字を返す。もっというなら、21474836 / 16807 = 1278なので、最大で1278秒 = 21.3分間は、1度目に同じ数字が出続ける。この現象が起こっているとは考えられないか？
• ちなみに、MSVCではdefault_random_engineはmt19937なので、この問題は発生しない。

知らず知らずのうちに罠にハマっていると「あれ？　なんじゃこりゃ？」ってことになってしまいそうだ。乱数を使われる皆様、ご注意あれ。