generates same number in Linux, but not in Windows

Here’s what’s going on:

  • default_random_engine in libstdc++ (GCC’s standard library) is minstd_rand0, which is a simple linear congruential engine:

    typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> minstd_rand0;
  • The way this engine generates random numbers is xi+1 = (16807xi + 0) mod 2147483647.

  • Therefore, if the seeds are different by 1, then most of the time the first generated number will differ by 16807.

  • The range of this generator is [1, 2147483646]. The way libstdc++’s uniform_int_distribution maps it to an integer in the range [1, 100] is essentially this: generate a number n. If the number is not greater than 2147483600, then return (n - 1) / 21474836 + 1; otherwise, try again with a new number.

    It should be easy to see that in the vast majority of cases, two ns that differ by only 16807 will yield the same number in [1, 100] under this procedure. In fact, one would expect the generated number to increase by one about every 21474836 / 16807 = 1278 seconds or 21.3 minutes, which agrees pretty well with your observations.

MSVC’s default_random_engine is mt19937, which doesn’t have this problem.

Leave a Comment