MacOS fornisce una funzione rand() non documentata in stdlib. Se lo lasci senza seeding, i primi valori che emette sono 16807, 282475249, 1622650073, 984943658 e 1144108930. Una rapida ricerca mostrerà che questa sequenza corrisponde a un generatore di numeri casuali LCG molto semplice che itera la seguente formula:
x n +1 =7 · x n (mod 2-1)
Poiché lo stato di questo RNG è descritto interamente dal valore di un singolo numero intero a 32 bit, il suo periodo non è molto lungo. Per essere precisi, si ripete ogni 2 − 2 iterazioni, emettendo ogni valore da 1 a 2 − 2.
Non credo che ci sia uno standard implementazione di rand() per tutte le versioni di Linux, ma esiste una funzione glibc rand() che viene spesso utilizzata. Invece di una singola variabile di stato a 32 bit, utilizza un pool di oltre 1000 bit, che a tutti gli effetti non produrrà mai una sequenza completamente ripetuta. Ancora una volta, probabilmente puoi scoprire quale versione hai stampando i primi output di questo RNG senza prima eseguirne il seeding. (La funzione glibc rand() produce i numeri 1804289383, 846930886, 1681692777, 1714636915 e 1957747793.)
Quindi il motivo per cui ricevi più collisioni in Linux (e quasi nessuna in MacOS) è che la versione Linux di rand() è fondamentalmente più casuale.
Anche se all'inizio potrebbe sembrare macOS rand() è in qualche modo migliore per non ripetere alcun numero, si dovrebbe notare che con questa quantità di numeri generati ci si aspetta di vedere molti duplicati (infatti, circa 790 milioni, o (2-1)/e ). Allo stesso modo, anche l'iterazione dei numeri in sequenza non produrrebbe duplicati, ma non sarebbe considerata molto casuale. Quindi il Linux rand() l'implementazione è in questo test indistinguibile da una vera fonte casuale, mentre macOS rand() non lo è.
Un'altra cosa che a prima vista sembra sorprendente è come macOS rand() può riuscire a evitare i duplicati così bene. Guardando il suo codice sorgente, troviamo che l'implementazione è la seguente:
/*
* 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));
Questo risulta effettivamente in tutti i numeri compresi tra 1 e RAND_MAX , inclusivo, esattamente una volta, prima che la sequenza si ripeta di nuovo. Poiché lo stato successivo è basato sulla moltiplicazione, lo stato non può mai essere zero (altrimenti anche tutti gli stati futuri sarebbero zero). Quindi il numero ripetuto che vedi è il primo, e zero è quello che non viene mai restituito.
Apple ha promosso l'uso di generatori di numeri casuali migliori nella loro documentazione ed esempi almeno da quando esiste macOS (o OS X), quindi la qualità di rand() probabilmente non è ritenuto importante e si sono semplicemente limitati a uno dei più semplici generatori pseudocasuali disponibili. (Come hai notato, il loro rand() è anche commentato con la raccomandazione di usare arc4random() invece.)
In una nota correlata, il più semplice generatore di numeri pseudocasuali che ho trovato che produce risultati decenti in questo (e molti altri) test per la casualità è xorshift*:
uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;
Questa implementazione si traduce in quasi esattamente 790 milioni di duplicati nel tuo test.
rand() è definito dallo standard C e lo standard C non specifica quale algoritmo utilizzare. Ovviamente, Apple sta usando un algoritmo inferiore alla tua implementazione GNU/Linux:quello Linux è indistinguibile da una vera fonte casuale nel tuo test, mentre l'implementazione Apple mescola solo i numeri.
Se vuoi numeri casuali di qualsiasi qualità, usa un PRNG migliore che dia almeno alcune garanzie sulla qualità dei numeri che restituisce, o semplicemente leggi da /dev/urandom o simili. Il successivo ti dà numeri di qualità crittografica, ma è lento. Anche se è troppo lento di per sé, /dev/urandom può fornire alcuni semi eccellenti a qualche altro PRNG più veloce.
In generale, la coppia rand/srand è stata per molto tempo considerata un po' deprecata a causa dei bit di ordine inferiore che mostrano meno casualità rispetto ai bit di ordine elevato nei risultati. Questo può o non può avere nulla a che fare con i tuoi risultati, ma penso che questa sia ancora una buona opportunità per ricordare che anche se alcune implementazioni rand/srand sono ora più aggiornate, le implementazioni precedenti persistono ed è meglio usare random(3 ). Sulla mia macchina Arch Linux, la seguente nota è ancora nella pagina man di 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.)
Appena sotto, la pagina man in realtà fornisce implementazioni di esempio molto brevi e molto semplici di rand e srand che riguardano i più semplici RNG LC che tu abbia mai visto e con un piccolo RAND_MAX. Non penso che corrispondano a ciò che è nella libreria standard C, se mai lo hanno fatto. O almeno spero di no.
In generale, se hai intenzione di utilizzare qualcosa dalla libreria standard, usa random se puoi (la pagina man lo elenca come standard POSIX fino a POSIX.1-2001, ma rand è standard molto prima che C fosse persino standardizzato) . O meglio ancora, apri Numerical Recipes (o cercalo online) o Knuth e implementane uno. Sono davvero facili e devi solo eseguirli una volta per avere un RNG generico con gli attributi di cui hai più spesso bisogno e che sia di qualità nota.