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なので、この問題は発生しない。
知らず知らずのうちに罠にハマっていると「あれ？ なんじゃこりゃ？」ってことになってしまいそうだ。乱数を使われる皆様、ご注意あれ。