<random> generuje tę samą liczbę w systemie Linux, ale nie w systemie Windows

Poniższy kod ma na celu wygenerowanie listy pięciu liczb pseudolosowych w przedziale [1100]. Zaszczepiam default_random_enginez time(0), co zwraca czas systemowy w czasie uniksowym . Kiedy kompiluję i uruchamiam ten program w systemie Windows 7 przy użyciu Microsoft Visual Studio 2013, działa zgodnie z oczekiwaniami (patrz poniżej). Kiedy robię to w Arch Linuxie z kompilatorem g ++, zachowuje się jednak dziwnie.

W Linuksie za każdym razem będzie generowanych 5 liczb. Ostatnie 4 liczby będą różne przy każdym wykonaniu (jak to często bywa), ale pierwsza liczba pozostanie taka sama.

Przykładowe dane wyjściowe z 5 wykonań w systemie Windows i 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

Dodając do tajemnicy, ta pierwsza liczba okresowo zwiększa się o jeden w systemie Linux. Po uzyskaniu powyższych wyników odczekałem około 30 minut i ponownie próbowałem stwierdzić, że pierwsza liczba uległa zmianie i teraz była zawsze generowana jako 26. Ciągle zwiększała się okresowo o 1 i wynosi teraz 32. Wydaje się, że odpowiada ze zmieniającą się wartością time(0).

Dlaczego pierwsza liczba rzadko zmienia się we wszystkich przebiegach, a kiedy tak się dzieje, zwiększa się o 1?

Kod. Dokładnie wypisuje 5 liczb i czas systemowy:

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

Oto co się dzieje:

• default_random_enginew libstdc ++ (standardowej bibliotece GCC) jest minstd_rand0, który jest prostym liniowym mechanizmem kongruencjalnym:

  typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> minstd_rand0;
  

• Sposób, w jaki ten silnik generuje liczby losowe, to x _{i + 1} = (16807x _i + 0) mod 2147483647.

• Dlatego jeśli nasiona różnią się o 1, w większości przypadków pierwsza wygenerowana liczba będzie się różnić o 16807.

• Zasięg tego generatora to [1, 2147483646]. Sposób, w jaki libstdc ++ uniform_int_distributionodwzorowuje to na liczbę całkowitą z zakresu [1, 100], jest zasadniczo taki: generuje liczbę n. Jeśli liczba nie jest większa niż 2147483600, zwróć (n - 1) / 21474836 + 1; w przeciwnym razie spróbuj ponownie z nowym numerem.

  Powinno być łatwo zauważyć, że w zdecydowanej większości przypadków dwa ns różniące się tylko o 16807 dadzą taką samą liczbę w [1, 100] w ramach tej procedury. W rzeczywistości można by oczekiwać, że wygenerowana liczba będzie rosła o jeden mniej więcej co 21474836/16807 = 1278 sekund lub 21,3 minuty, co całkiem dobrze zgadza się z twoimi obserwacjami.

MSVC default_random_engineto mt19937, który nie ma tego problemu.

Definicja std::default_random_engineimplementacji. Użyj std::mt19937lub std::mt19937_64zamiast.

W dodatku std::time, a ctimefunkcje nie są bardzo dokładne, używać typów zdefiniowanych w <chrono>nagłówku zamiast:

#include <iostream>
#include <random>
#include <chrono>

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

    auto t = std::chrono::high_resolution_clock::now().time_since_epoch().count();

    std::mt19937 e;
    e.seed(static_cast<unsigned int>(t)); //Seed engine with timed value.
    std::uniform_int_distribution<int> u(lower_bound, upper_bound);

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

    for (int counter = 1; counter <= 5; counter++)
    {
        int secret = u(e);

        std::cout << secret << '\t' << t << std::endl;
    }   

    system("pause");
    return 0;
}

W Linuksie funkcja losowa nie jest funkcją losową w probabilistycznym sensie, ale generatorem liczb pseudolosowych. Jest solony z nasionami, a na podstawie tego ziarna produkowane liczby są pseudolosowe i równomiernie rozłożone. Sposób Linuksa ma tę zaletę, że przy projektowaniu pewnych eksperymentów z wykorzystaniem informacji pochodzących z populacji można zmierzyć powtórzenie eksperymentu ze znanymi poprawkami informacji wejściowych. Gdy końcowy program jest gotowy do rzeczywistych testów, można utworzyć sól (ziarno), prosząc użytkownika o poruszenie myszą, zmieszanie ruchu myszy z kilkoma naciśnięciami klawiszy i dodanie kreski liczby mikrosekund od początku ostatnie włączenie.

Ziarno liczb losowych systemu Windows jest uzyskiwane ze zbioru liczb myszy, klawiatury, sieci i pory dnia. Nie jest to powtarzalne. Ale tę wartość soli można zresetować do znanego ziarna, jeśli jak wspomniano powyżej, ktoś jest zaangażowany w projekt eksperymentu.

O tak, Linux ma dwa generatory liczb losowych. Jeden, domyślny to modulo 32 bity, a drugi to modulo 64 bity. Twój wybór zależy od potrzeb w zakresie dokładności i ilości czasu obliczeniowego, który chcesz przeznaczyć na testowanie lub faktyczne użycie.