Pourquoi rand () répète-t-il les nombres beaucoup plus souvent sur Linux que sur Mac?

J'implémentais une table de hachage en C dans le cadre d'un projet sur lequel je travaille et j'utilise des insertions aléatoires pour le tester lorsque j'ai remarqué que rand()sous Linux, il semble répéter les nombres beaucoup plus souvent que sur Mac. RAND_MAXest 2147483647 / 0x7FFFFFFF sur les deux plates-formes. Je l'ai réduit à ce programme de test qui fait un tableau d'octets de RAND_MAX+1long, génère RAND_MAXdes nombres aléatoires, note si chacun est un doublon et le vérifie dans la liste comme on le voit.

#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 génère régulièrement environ 790 millions de doublons. Mac n'en génère systématiquement qu'un, de sorte qu'il parcourt chaque nombre aléatoire qu'il peut générer presque sans répétition. Quelqu'un peut-il m'expliquer comment cela fonctionne? Je ne peux rien dire de différent des pages de manuel, je ne peux pas dire quel RNG chacun utilise et je ne trouve rien en ligne. Merci!

Alors qu'au début, il peut sembler que macOS rand()est en quelque sorte meilleur pour ne pas répéter de chiffres, il convient de noter qu'avec cette quantité de chiffres générés, il devrait voir beaucoup de doublons (en fait, environ 790 millions, ou (2 ³¹ -1 ) / e ). De même, l'itération à travers les nombres dans l'ordre ne produirait pas non plus de doublons, mais ne serait pas considérée comme très aléatoire. Ainsi, l' rand()implémentation Linux est dans ce test indiscernable d'une véritable source aléatoire, contrairement à macOS rand().

Une autre chose qui semble surprenante à première vue est de savoir comment 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 compris 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 nul (ou tous les états futurs seraient également nuls). 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) a existé, de sorte que la qualité de rand()n'est probablement pas jugée importante, et ils sont juste restés avec l'un des les 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'utilisation à la arc4random()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 (et beaucoup d'autres) tests d'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.

MacOS fournit une fonction rand () non documentée dans stdlib. Si vous ne le laissez pas, les premières valeurs qu'il génère 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 réitère la formule suivante:

x _{n +1} = 7 ⁵ · x _n (mod 2 ³¹ - 1)

Étant donné que l'état de ce RNG est entièrement décrit par la valeur d'un seul entier 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 chaque valeur de 1 à 2 ³¹ - 2.

Je ne pense pas qu'il existe une implémentation standard 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 32 bits, celle-ci 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 découvrir quelle version vous avez en imprimant les premières sorties de ce RNG sans l'amorcer d'abord. (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 pas sous MacOS) est que la version Linux de rand () est fondamentalement plus aléatoire.

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 Apple mélange simplement 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 retourne, ou lisez simplement /dev/urandomou similaire. Le dernier vous donne des numéros de qualité cryptographique, mais est lent. Même s'il est trop lent par lui-même, il /dev/urandompeut fournir d'excellentes graines à un autre PRNG plus rapide.

En général, la paire rand / srand a été considérée comme obsolète depuis 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 aléatoire (3 ). Sur ma boîte 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 d'implémentation très courts et très simples 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, si c'est le cas. 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 vers POSIX.1-2001, mais rand est un moyen standard avant que C ne soit même standardisé) . Ou mieux encore, ouvrez les recettes numériques (ou recherchez-les en ligne) ou Knuth et implémentez-en une. 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.