Dlaczego rand () powtarza liczby znacznie częściej w systemie Linux niż Mac?

Wdrażałem hashap w C jako część projektu, nad którym pracuję i używam losowych wstawek do testowania go, gdy zauważyłem, że rand()w Linuksie wydaje się powtarzać liczby znacznie częściej niż na Macu. RAND_MAXto 2147483647 / 0x7FFFFFFF na obu platformach. Sprowadziłem go do tego programu testowego, który tworzy tablicę bajtów RAND_MAX+1-długą, generuje RAND_MAXliczby losowe, zauważa, czy każdy z nich jest duplikatem, i sprawdza go z listy, jak widać.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int main() {
    size_t size = ((size_t)RAND_MAX) + 1;
    char *randoms = calloc(size, sizeof(char));
    int dups = 0;
    srand(time(0));
    for (int i = 0; i < RAND_MAX; i++) {
        int r = rand();
        if (randoms[r]) {
            // printf("duplicate at %d\n", r);
            dups++;
        }
        randoms[r] = 1;
    }
    printf("duplicates: %d\n", dups);
}

Linux konsekwentnie generuje około 790 milionów duplikatów. Mac konsekwentnie generuje tylko jeden, więc zapętla każdą losową liczbę, którą może wygenerować prawie bez powtarzania. Czy ktoś może mi wyjaśnić, jak to działa? Nie mogę powiedzieć nic innego niż strony podręcznika, nie mogę powiedzieć, którego RNG używa i nie mogę znaleźć niczego online. Dzięki!

Choć na początku może się wydawać, że macOS rand()jest w jakiś sposób lepszy, jeśli nie powtarza żadnych liczb, należy zauważyć, że przy takiej liczbie wygenerowanych liczb oczekuje się dużej liczby duplikatów (w rzeczywistości około 790 milionów lub (2 ³¹ -1) ) / e ). Podobnie powtarzanie liczb w sekwencji również nie spowodowałoby duplikatów, ale nie byłoby uważane za bardzo przypadkowe. Tak więc rand()implementacja Linuksa jest w tym teście nie do odróżnienia od prawdziwego losowego źródła, podczas gdy macOS rand()nie.

Inną rzeczą, która wydaje się zaskakująca na pierwszy rzut oka, jest sposób, w jaki macOS rand()potrafi tak dobrze unikać duplikatów. Patrząc na jego kod źródłowy , stwierdzamy, że implementacja wygląda następująco:

/*
 * Compute x = (7^5 * x) mod (2^31 - 1)
 * without overflowing 31 bits:
 *      (2^31 - 1) = 127773 * (7^5) + 2836
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
    long hi, lo, x;

    /* Can't be initialized with 0, so use another value. */
    if (*ctx == 0)
        *ctx = 123459876;
    hi = *ctx / 127773;
    lo = *ctx % 127773;
    x = 16807 * lo - 2836 * hi;
    if (x < 0)
        x += 0x7fffffff;
    return ((*ctx = x) % ((unsigned long) RAND_MAX + 1));

To rzeczywiście powoduje, że wszystkie liczby od 1 do RAND_MAXwłącznie, dokładnie jeden raz, przed powtórzeniem sekwencji. Ponieważ następny stan opiera się na pomnożeniu, stan nigdy nie może wynosić zero (lub wszystkie przyszłe stany również będą zerowe). Zatem powtarzana liczba, którą widzisz, jest pierwsza, a zero to ta, która nigdy nie jest zwracana.

Apple promuje stosowanie lepszych generatorów liczb losowych w ich dokumentacji i przykładach przez co najmniej tak długo, jak istnieje macOS (lub OS X), więc jakość rand()prawdopodobnie nie jest uważana za ważną i po prostu utknęli w jednym z najprostsze dostępne generatory pseudolosowe. (Jak już zauważyłeś, ich rand()komentarz został nawet opatrzony zaleceniem użycia arc4random()).

W pokrewnej uwadze, najprostszym generatorem liczb pseudolosowych, jaki udało mi się znaleźć, który daje przyzwoite wyniki w tym (i wielu innych) testach losowości, jest xorshift * :

uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;

Ta implementacja daje prawie dokładnie 790 milionów duplikatów w teście.

MacOS zapewnia nieudokumentowaną funkcję rand () w stdlib. Jeśli pozostawisz to bez nasion, pierwsze wartości, które wyśle ​​to 16807, 282475249, 1622650073, 984943658 i 1144108930. Szybkie wyszukiwanie pokaże, że ta sekwencja odpowiada bardzo prostemu generatorowi liczb losowych LCG, który iteruje następującą formułę:

x _{n + 1} = 7 ⁵ · x _n (mod 2 ³¹ - 1)

Ponieważ stan tego RNG jest opisany w całości przez wartość pojedynczej 32-bitowej liczby całkowitej, jego okres nie jest bardzo długi. Mówiąc ściślej, powtarza się co 2 ³¹ - 2 iteracji, generując każdą wartość od 1 do 2 ³¹ - 2.

Nie sądzę, aby istniała standardowa implementacja rand () dla wszystkich wersji Linuksa, ale często używana jest funkcja rand () glibc . Zamiast pojedynczej 32-bitowej zmiennej stanu wykorzystuje to pulę ponad 1000 bitów, która zgodnie ze wszystkimi celami i celami nigdy nie wytworzy w pełni powtarzalnej sekwencji. Ponownie, prawdopodobnie możesz dowiedzieć się, jaką wersję posiadasz, drukując kilka pierwszych wyników z tego RNG bez wcześniejszego uruchamiania. (Funkcja rand () glibc generuje liczby 1804289383, 846930886, 1681692777, 1714636915 i 1957747793.)

Powodem, dla którego masz więcej kolizji w Linuksie (a prawie wcale w MacOS) jest to, że wersja rand () Linuksa jest w zasadzie bardziej losowa.

rand()jest zdefiniowany przez standard C, a standard C nie określa, którego algorytmu użyć. Oczywiście Apple używa gorszego algorytmu do implementacji GNU / Linux: Linuksa nie można odróżnić od prawdziwego losowego źródła w teście, podczas gdy implementacja Apple po prostu przetasowuje liczby.

Jeśli chcesz losowych liczb dowolnej jakości, albo użyj lepszego PRNG, który daje przynajmniej pewne gwarancje jakości liczb, które zwraca, lub po prostu odczytaj z /dev/urandomlub podobny. Później daje kryptograficzne wartości jakości, ale jest powolny. Nawet jeśli sam jest zbyt wolny, /dev/urandommoże zapewnić doskonałe nasiona innym, szybszym PRNG.

Ogólnie rzecz biorąc, para rand / srand była uważana za przestarzałą przez długi czas z powodu bitów niskiego rzędu, które wykazują mniej losowości niż bity wysokiego rzędu w wynikach. To może, ale nie musi mieć nic wspólnego z twoimi wynikami, ale myślę, że nadal jest to dobra okazja, aby pamiętać, że mimo iż niektóre implementacje rand / srand są teraz bardziej aktualne, starsze implementacje są nadal dostępne i lepiej używać losowych (3). ). W moim Arch Linuxie następująca uwaga jest wciąż na stronie podręcznika dla rand (3):

  The versions of rand() and srand() in the Linux C Library use the  same
   random number generator as random(3) and srandom(3), so the lower-order
   bits should be as random as the higher-order bits.  However,  on  older
   rand()  implementations,  and  on  current implementations on different
   systems, the lower-order bits are much less random than the  higher-or-
   der bits.  Do not use this function in applications intended to be por-
   table when good randomness is needed.  (Use random(3) instead.)

Tuż poniżej tego strona podręcznika podaje bardzo krótkie, bardzo proste przykładowe implementacje rand i srand, które dotyczą najprostszych LC RNG, jakie kiedykolwiek widziałeś i mają małą RAND_MAX. Nie sądzę, żeby pasowały do ​​tego, co jest w standardowej bibliotece C, jeśli kiedykolwiek tak było. A przynajmniej mam nadzieję, że nie.

Zasadniczo, jeśli zamierzasz użyć czegoś ze standardowej biblioteki, użyj losowo, jeśli możesz (strona podręcznika wymienia to jako standard POSIX z powrotem do POSIX.1-2001, ale rand jest standardem znacznie wcześniej niż C został znormalizowany) . Albo jeszcze lepiej: otwórz przepisy numeryczne (lub poszukaj ich online) lub Knuth i zaimplementuj je. Są naprawdę łatwe i naprawdę musisz to zrobić tylko raz, aby mieć RNG ogólnego przeznaczenia z atrybutami, których najczęściej potrzebujesz i który ma znaną jakość.