Warum wiederholt rand() Zahlen viel öfter unter Linux als auf Mac?

Ich habe im Rahmen eines Projekts, an dem ich arbeite, eine Hashmap in C implementiert und zufällige Einfügungen verwendet, um sie zu testen. ich habe bemerkt, dass rand() Unter Linux scheinen sich Zahlen viel öfter zu wiederholen als unter Mac. RAND_MAX ist 2147483647/0x7FFFFFFF auf beiden Plattformen. Ich habe es auf dieses Testprogramm reduziert, das ein Byte-Array erstellt RAND_MAX+1-lang, erzeugt RAND_MAX Zufallszahlen, stellt fest, ob es sich jeweils um ein Duplikat handelt, und streicht es wie gesehen von der Liste.

#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 generiert ständig rund 790 Millionen Duplikate. Der Mac generiert konsequent nur eine, also durchläuft er jede Zufallszahl, die er generieren kann fast ohne zu wiederholen. Kann mir bitte jemand erklären, wie das funktioniert? Ich kann nichts anderes sagen als die man Seiten, kann nicht sagen, welches RNG jeweils verwendet wird, und kann online nichts finden. Vielen Dank!

Während es zunächst wie das macOS klingen mag rand() ist irgendwie besser, keine Zahlen zu wiederholen, man sollte beachten, dass dies bei dieser Menge an generierten Zahlen der Fall ist erwartet viele Duplikate zu sehen (tatsächlich rund 790 Millionen oder (2³¹-1)/e). Ebenso würde das Durchlaufen der Zahlen nacheinander keine Duplikate erzeugen, aber nicht als sehr zufällig angesehen werden. Also das Linux rand() Umsetzung ist bei dieser Prüfung nicht von einer echten Zufallsquelle zu unterscheiden, während das macOS rand() ist nicht.

Auf den ersten Blick überraschend erscheint auch, wie das macOS rand() kann es so gut schaffen, Duplikate zu vermeiden. Anschauen seinen Quellcodefinden wir die Implementierung wie folgt:

/*
 * 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));

Dies ergibt tatsächlich alle Zahlen zwischen 1 und RAND_MAX, einschließlich, genau einmal, bevor sich die Sequenz erneut wiederholt. Da der nächste Zustand auf Multiplikation basiert, kann der Zustand niemals Null sein (sonst wären alle zukünftigen Zustände ebenfalls Null). Daher ist die wiederholte Zahl, die Sie sehen, die erste, und Null ist diejenige, die nie zurückgegeben wird.

Apple fördert die Verwendung besserer Zufallszahlengeneratoren in seiner Dokumentation und seinen Beispielen mindestens so lange, wie es macOS (oder OS X) gibt, daher die Qualität von rand() wird wahrscheinlich nicht als wichtig erachtet, und sie haben sich einfach an einen der einfachsten verfügbaren Pseudozufallsgeneratoren gehalten. (Wie Sie bemerkt haben, ihre rand() ist sogar mit einer Anwendungsempfehlung kommentiert arc4random() stattdessen.)

In diesem Zusammenhang ist der einfachste Pseudozufallszahlengenerator, den ich finden konnte und der bei diesem (und vielen anderen) Tests auf Zufälligkeit anständige Ergebnisse liefert, xorshift*:

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

Diese Implementierung führt in Ihrem Test zu ziemlich genau 790 Millionen Duplikaten.

MacOS bietet eine undokumentierte rand()-Funktion in stdlib. Wenn Sie es nicht gesetzt lassen, sind die ersten ausgegebenen Werte 16807, 282475249, 1622650073, 984943658 und 1144108930. A schnelle Suche wird zeigen, dass diese Sequenz einem sehr einfachen LCG-Zufallszahlengenerator entspricht, der die folgende Formel iteriert:

x_n+1 = 7⁵ · x_n (Mod 2³¹ − 1)

Da der Zustand dieses RNG vollständig durch den Wert einer einzelnen 32-Bit-Ganzzahl beschrieben wird, ist seine Periode nicht sehr lang. Genauer gesagt wiederholt es sich alle 2³¹ − 2 Iterationen, wobei jeder Wert von 1 bis 2 ausgegeben wird³¹ − 2.

Ich glaube nicht, dass es eine gibt Standard Implementierung von rand() für alle Versionen von Linux, aber es gibt eine glibc rand()-Funktion das wird oft verwendet. Anstelle einer einzelnen 32-Bit-Zustandsvariablen wird hier ein Pool von über 1000 Bits verwendet, was praktisch nie eine sich vollständig wiederholende Sequenz erzeugen wird. Auch hier können Sie wahrscheinlich herausfinden, welche Version Sie haben, indem Sie die ersten Ausgaben dieses RNG drucken, ohne es zuerst zu impfen. (Die Funktion glibc rand() erzeugt die Zahlen 1804289383, 846930886, 1681692777, 1714636915 und 1957747793.)

Der Grund, warum Sie unter Linux mehr Kollisionen bekommen (und kaum welche unter MacOS), ist, dass die Linux-Version von rand() im Grunde zufälliger ist.

rand() wird durch den C-Standard definiert, und der C-Standard gibt nicht an, welcher Algorithmus zu verwenden ist. Offensichtlich verwendet Apple einen schlechteren Algorithmus als Ihre GNU/Linux-Implementierung: Der Linux-Algorithmus ist in Ihrem Test nicht von einer echten Zufallsquelle zu unterscheiden, während die Apple-Implementierung nur die Zahlen mischt.

Wenn Sie Zufallszahlen beliebiger Qualität wünschen, verwenden Sie entweder einen besseren PRNG, der zumindest einige Garantien für die Qualität der zurückgegebenen Zahlen gibt, oder lesen Sie einfach aus /dev/urandom oder ähnliches. Letzteres gibt Ihnen Zahlen in kryptografischer Qualität, ist aber langsam. Auch wenn es alleine zu langsam ist, /dev/urandom kann einige ausgezeichnete Samen für ein anderes, schnelleres PRNG liefern.

Im Allgemeinen wurde das rand/srand-Paar lange Zeit als veraltet angesehen, da niederwertige Bits in den Ergebnissen weniger Zufälligkeit aufweisen als höherwertige Bits. Dies kann etwas mit Ihren Ergebnissen zu tun haben oder auch nicht, aber ich denke, dies ist immer noch eine gute Gelegenheit, sich daran zu erinnern, dass, obwohl einige rand/srand-Implementierungen jetzt aktueller sind, ältere Implementierungen bestehen bleiben und es besser ist, random(3 ). Auf meiner Arch-Linux-Box ist der folgende Hinweis immer noch in der Manpage für 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.)

Direkt darunter gibt die Manpage tatsächlich sehr kurze, sehr einfache Beispielimplementierungen von rand und srand, die ungefähr die einfachsten LC-RNGs sind, die Sie je gesehen haben, und die einen kleinen RAND_MAX haben. Ich glaube nicht, dass sie mit dem übereinstimmen, was in der C-Standardbibliothek enthalten ist, falls dies jemals der Fall war. Oder zumindest hoffe ich nicht.

Wenn Sie etwas aus der Standardbibliothek verwenden möchten, verwenden Sie im Allgemeinen random, wenn Sie können (die Manpage listet es als POSIX-Standard bis POSIX.1-2001 auf, aber rand ist Standard, lange bevor C überhaupt standardisiert wurde). . Oder noch besser, knacken Sie Numerical Recipes (oder suchen Sie online danach) oder Knuth und implementieren Sie eines. Sie sind wirklich einfach und Sie müssen es nur einmal tun, um einen Allzweck-RNG mit den Attributen zu haben, die Sie am häufigsten benötigen, und der von bekannter Qualität ist.