MacOS bietet eine undokumentierte rand()-Funktion in stdlib. Wenn Sie es nicht gesetzt lassen, sind die ersten Werte, die es ausgibt, 16807, 282475249, 1622650073, 984943658 und 1144108930. Eine schnelle Suche zeigt, 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 und gibt jeden Wert von 1 bis 2 − 2 aus.
Ich glaube nicht, dass es einen Standard gibt Implementierung von rand() für alle Linux-Versionen, aber es gibt eine glibc rand()-Funktion, die häufig verwendet wird. 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 mehr zufällig ist.
Während es sich zunächst wie das macOS rand() anhört irgendwie besser ist, keine Zahlen zu wiederholen, sollte man beachten, dass bei dieser Menge an generierten Zahlen viele Duplikate zu erwarten sind (tatsächlich etwa 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() Implementierung ist in diesem Test nicht von einer echten Zufallsquelle zu unterscheiden, während die macOS rand() ist nicht.
Auf den ersten Blick überraschend erscheint auch, wie das macOS rand() kann es so gut schaffen, Duplikate zu vermeiden. Wenn wir uns den Quellcode ansehen, finden 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, sind ihre rand() wird sogar mit einer Empfehlung zur Verwendung von arc4random() kommentiert 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.
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 hervorragende 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 wirklich 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.