MacOS poskytuje nezdokumentovanou funkci rand() ve stdlib. Pokud ji necháte nenasazenou, pak první hodnoty, které vypíše, jsou 16807, 282475249, 1622650073, 984943658 a 1144108930. Rychlé vyhledávání ukáže, že tato sekvence odpovídá velmi základnímu generátoru náhodných čísel LCG, který iteruje následující vzorec:
x n +1 =7 · x n (mod 2 − 1)
Protože stav tohoto RNG je celý popsán hodnotou jednoho 32bitového celého čísla, jeho perioda není příliš dlouhá. Abychom byli přesní, opakuje se každé 2 − 2 iterace a vydává každou hodnotu od 1 do 2 − 2.
Nemyslím si, že existuje standard implementace rand() pro všechny verze Linuxu, ale často se používá funkce glibc rand(). Namísto jediné 32bitové stavové proměnné to používá fond o více než 1000 bitech, který ze všech důvodů nikdy nevytvoří plně se opakující sekvenci. Opět můžete pravděpodobně zjistit, jakou verzi máte, vytištěním prvních několika výstupů z tohoto RNG, aniž byste jej nejprve nasévali. (Funkce glibc rand() vytváří čísla 1804289383, 846930886, 1681692777, 1714636915 a 1957747793.)
Takže důvod, proč máte v Linuxu více kolizí (a v MacOS téměř žádné), je ten, že linuxová verze rand() je v podstatě náhodnější.
I když to zpočátku může znít jako macOS rand() je nějak lepší pro neopakování žádných čísel, je třeba poznamenat, že s tímto množstvím generovaných čísel se očekává, že bude vidět spousta duplikátů (ve skutečnosti kolem 790 milionů, neboli (2-1)/e ). Podobně opakování čísel v sekvenci by také neprodukovalo žádné duplikáty, ale nebylo by považováno za příliš náhodné. Takže Linux rand() implementace je v tomto testu k nerozeznání od skutečného náhodného zdroje, zatímco macOS rand() není.
Další věc, která se na první pohled zdá překvapivá, je způsob, jakým macOS rand() dokáže se tak dobře vyhnout duplikátům. Při pohledu na jeho zdrojový kód zjistíme, že implementace je následující:
/*
* 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));
Výsledkem jsou skutečně všechna čísla mezi 1 a RAND_MAX , včetně, přesně jednou, než se sekvence znovu opakuje. Protože další stav je založen na násobení, nemůže být stav nikdy nulový (nebo by všechny budoucí stavy byly také nulové). Opakované číslo, které vidíte, je tedy první a nula je to, které se nikdy nevrací.
Apple ve své dokumentaci a příkladech propaguje používání lepších generátorů náhodných čísel minimálně tak dlouho, dokud existuje macOS (nebo OS X), takže kvalita rand() pravděpodobně není považováno za důležité a právě zůstali u jednoho z nejjednodušších dostupných pseudonáhodných generátorů. (Jak jste si všimli, jejich rand() je dokonce komentován doporučením použít arc4random() místo toho.)
V související poznámce, nejjednodušší generátor pseudonáhodných čísel, který jsem našel a který poskytuje slušné výsledky v tomto (a mnoha dalších) testech náhodnosti, je xorshift*:
uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;
Výsledkem této implementace je téměř přesně 790 milionů duplikátů ve vašem testu.
rand() je definován standardem C a standard C nespecifikuje, který algoritmus se má použít. Je zřejmé, že Apple používá podřadný algoritmus než vaše implementace GNU/Linux:Ten Linux je ve vašem testu k nerozeznání od skutečného náhodného zdroje, zatímco implementace Apple jen zamíchá čísla.
Pokud chcete náhodná čísla jakékoli kvality, použijte lepší PRNG, který poskytuje alespoň nějaké záruky kvality vracených čísel, nebo jednoduše čtěte z /dev/urandom nebo podobné. Pozdější poskytuje čísla kryptografické kvality, ale je pomalá. I když je sám o sobě příliš pomalý, /dev/urandom může poskytnout vynikající semena nějakému jinému, rychlejšímu PRNG.
Obecně platí, že pár rand/srand byl po dlouhou dobu považován za zastaralý, protože bity nižšího řádu vykazují ve výsledcích menší náhodnost než bity vyššího řádu. To může, ale nemusí mít nic společného s vašimi výsledky, ale myslím si, že je to stále dobrá příležitost si připomenout, že i když jsou některé implementace rand/srand nyní aktuálnější, starší implementace přetrvávají a je lepší použít náhodné (3 ). Na mém boxu s Arch Linuxem je v manuálové stránce pro rand(3) stále následující poznámka:
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.)
Těsně pod tím manuálová stránka ve skutečnosti poskytuje velmi krátké, velmi jednoduché příklady implementací rand a srand, které jsou asi nejjednoduššími LC RNG, jaké jste kdy viděli, a mají malý RAND_MAX. Nemyslím si, že odpovídají tomu, co je ve standardní knihovně C, pokud někdy ano. Nebo alespoň doufám.
Obecně platí, že pokud se chystáte použít něco ze standardní knihovny, použijte náhodné, pokud můžete (manuálová stránka to uvádí jako standard POSIX zpět do POSIX.1-2001, ale rand je standardní daleko dříve, než bylo dokonce standardizováno C) . Nebo ještě lépe, otevřete Numerické recepty (nebo je vyhledejte online) nebo Knuth a jeden implementujte. Jsou opravdu snadné a stačí to udělat jen jednou, abyste měli RNG pro obecné použití s atributy, které nejčastěji potřebujete, a které mají známou kvalitu.