<random> generates same number in Linux, but not in Windows

Question

The code below is meant to generate a list of five pseudo-random numbers in the interval [1,100]. I seed the default_random_engine with time(0), which returns the system time in unix time. When I compile and run this program on Windows 7 using Microsoft Visual Studio 2013, it works as expected (see below). When I do so in Arch Linux with the g++ compiler, however, it behaves strangely.

In Linux, 5 numbers will be generated each time. The last 4 numbers will be different on each execution (as will often be the case), but the first number will stay the same.

Example output from 5 executions on Windows and 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

Adding to the mystery, that first number periodically increments by one on Linux. After obtaining the above outputs, I waited about 30 minutes and tried again to find that the 1st number had changed and now was always being generated as a 26. It has continued to increment by 1 periodically and is now at 32. It seems to correspond with the changing value of time(0).

Why does the first number rarely change across runs, and then when it does, increment by 1?

The code. It neatly prints out the 5 numbers and the system time:

#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;
}

Answer 1

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 x_i+1 = (16807x_i + 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.