MacOS fournit une fonction rand() non documentée dans stdlib. Si vous ne le laissez pas, les premières valeurs qu'il produit sont 16807, 282475249, 1622650073, 984943658 et 1144108930. Une recherche rapide montrera que cette séquence correspond à un générateur de nombres aléatoires LCG très basique qui itère la formule suivante :
x n +1 =7 · x n (mode 2 − 1)
L'état de ce RNG étant entièrement décrit par la valeur d'un seul entier de 32 bits, sa période n'est pas très longue. Pour être précis, il se répète toutes les 2 − 2 itérations, produisant toutes les valeurs de 1 à 2 − 2.
Je ne pense pas qu'il y ait une norme implémentation de rand() pour toutes les versions de Linux, mais il existe une fonction glibc rand() qui est souvent utilisée. Au lieu d'une seule variable d'état de 32 bits, cela utilise un pool de plus de 1000 bits, qui à toutes fins utiles ne produira jamais une séquence entièrement répétitive. Encore une fois, vous pouvez probablement savoir quelle version vous avez en imprimant les premières sorties de ce RNG sans l'ensemencer au préalable. (La fonction glibc rand() produit les nombres 1804289383, 846930886, 1681692777, 1714636915 et 1957747793.)
Donc, la raison pour laquelle vous obtenez plus de collisions sous Linux (et presque aucune sous MacOS) est que la version Linux de rand() est fondamentalement plus aléatoire.
Alors qu'au début, cela peut ressembler à macOS rand() est en quelque sorte préférable de ne répéter aucun nombre, il convient de noter qu'avec cette quantité de nombres générés, on s'attend à voir beaucoup de doublons (en fait, environ 790 millions, ou (2-1)/e ). De même, parcourir les nombres dans l'ordre ne produirait également aucun doublon, mais ne serait pas considéré comme très aléatoire. Donc Linux rand() l'implémentation est dans ce test impossible à distinguer d'une véritable source aléatoire, alors que macOS rand() n'est pas.
Une autre chose qui semble surprenante à première vue est la façon dont le macOS rand() peut si bien éviter les doublons. En regardant son code source, nous constatons que l'implémentation est la suivante :
/*
* 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));
Cela se traduit en effet par tous les nombres entre 1 et RAND_MAX , inclus, exactement une fois, avant que la séquence ne se répète à nouveau. Étant donné que l'état suivant est basé sur la multiplication, l'état ne peut jamais être zéro (ou tous les états futurs seraient également zéro). Ainsi, le nombre répété que vous voyez est le premier, et zéro est celui qui n'est jamais renvoyé.
Apple promeut l'utilisation de meilleurs générateurs de nombres aléatoires dans sa documentation et ses exemples depuis au moins aussi longtemps que macOS (ou OS X) existe, donc la qualité de rand() n'est probablement pas considéré comme important, et ils se contentent de l'un des générateurs pseudo-aléatoires les plus simples disponibles. (Comme vous l'avez noté, leur rand() est même commenté avec une recommandation d'utiliser arc4random() à la place.)
Sur une note connexe, le générateur de nombres pseudo-aléatoires le plus simple que j'ai pu trouver et qui produit des résultats décents dans ce test (et bien d'autres) pour le caractère aléatoire est xorshift* :
uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;
Cette implémentation génère presque exactement 790 millions de doublons dans votre test.
rand() est défini par la norme C, et la norme C ne spécifie pas quel algorithme utiliser. De toute évidence, Apple utilise un algorithme inférieur à votre implémentation GNU/Linux :celui de Linux est indiscernable d'une véritable source aléatoire dans votre test, tandis que l'implémentation d'Apple ne fait que mélanger les chiffres.
Si vous voulez des nombres aléatoires de n'importe quelle qualité, utilisez un meilleur PRNG qui donne au moins quelques garanties sur la qualité des nombres qu'il renvoie, ou lisez simplement à partir de /dev/urandom ou similaire. Ce dernier vous donne des numéros de qualité cryptographique, mais est lent. Même s'il est trop lent en soi, /dev/urandom peut fournir d'excellentes graines à d'autres PRNG plus rapides.
En général, la paire rand/srand a été considérée comme obsolète pendant longtemps en raison des bits de poids faible affichant moins de caractère aléatoire que les bits de poids fort dans les résultats. Cela peut ou non avoir quelque chose à voir avec vos résultats, mais je pense que c'est toujours une bonne occasion de se rappeler que même si certaines implémentations rand/srand sont maintenant plus à jour, les implémentations plus anciennes persistent et il est préférable d'utiliser random(3 ). Sur ma machine Arch Linux, la note suivante est toujours dans la page de manuel de 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.)
Juste en dessous, la page de manuel donne en fait des exemples très courts et très simples d'implémentations de rand et srand qui concernent les RNG LC les plus simples que vous ayez jamais vus et ayant un petit RAND_MAX. Je ne pense pas qu'ils correspondent à ce qui se trouve dans la bibliothèque standard C, s'ils l'ont déjà fait. Ou du moins j'espère que non.
En général, si vous allez utiliser quelque chose de la bibliothèque standard, utilisez random si vous le pouvez (la page de manuel le répertorie comme standard POSIX depuis POSIX.1-2001, mais rand est standard bien avant que C ne soit même standardisé) . Ou mieux encore, ouvrez Numerical Recipes (ou recherchez-le en ligne) ou Knuth et implémentez-en un. Ils sont vraiment faciles et vous n'avez vraiment besoin de le faire qu'une seule fois pour avoir un RNG à usage général avec les attributs dont vous avez le plus souvent besoin et qui est de qualité connue.