¿Por qué rand () repite números con mucha más frecuencia en Linux que en Mac?

Estaba implementando un hashmap en C como parte de un proyecto en el que estoy trabajando y usando inserciones aleatorias para probarlo cuando noté que rand()en Linux parece repetir números con mucha más frecuencia que en Mac. RAND_MAXes 2147483647 / 0x7FFFFFFF en ambas plataformas. Lo reduje a este programa de prueba que crea una matriz de bytes de RAND_MAX+1largo, genera RAND_MAXnúmeros aleatorios, anota si cada uno es un duplicado y lo elimina de la lista como se ve.

#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 genera constantemente alrededor de 790 millones de duplicados. Mac consistentemente solo genera uno, por lo que recorre cada número aleatorio que puede generar casi sin repetir. ¿Alguien puede explicarme cómo funciona esto? No puedo decir nada diferente de las páginas del manual, no puedo decir qué RNG está usando cada una, y no puedo encontrar nada en línea. ¡Gracias!

Si bien al principio puede parecer rand()que macOS es de alguna manera mejor para no repetir ningún número, uno debe tener en cuenta que con esta cantidad de números generados se espera ver muchos duplicados (de hecho, alrededor de 790 millones, o (2 ³¹ -1 ) / e ). Asimismo, iterar a través de los números en secuencia tampoco produciría duplicados, pero no se consideraría muy aleatorio. Por lo tanto, la rand()implementación de Linux en esta prueba no se puede distinguir de una fuente aleatoria verdadera, mientras que macOS rand()no lo es.

Otra cosa que parece sorprendente a primera vista es cómo MacOS rand()puede manejar evitar los duplicados tan bien. Mirando su código fuente , encontramos que la implementación es la siguiente:

/*
 * 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));

De hecho, esto da como resultado todos los números entre 1 e RAND_MAX, inclusive, exactamente una vez, antes de que la secuencia se repita nuevamente. Como el siguiente estado se basa en la multiplicación, el estado nunca puede ser cero (o todos los estados futuros también serían cero). Por lo tanto, el número repetido que ve es el primero, y cero es el que nunca se devuelve.

Apple ha estado promoviendo el uso de mejores generadores de números aleatorios en su documentación y ejemplos durante al menos el tiempo que ha existido macOS (u OS X), por lo que la calidad de rand()probablemente no se considera importante, y simplemente se han quedado con uno de Los generadores pseudoaleatorios más simples disponibles. (Como notó, rand()incluso se comenta con una recomendación para usar arc4random()en su lugar).

En una nota relacionada, el generador de números pseudoaleatorio más simple que pude encontrar que produce resultados decentes en esta (y muchas otras) pruebas de aleatoriedad es xorshift * :

uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;

Esta implementación resulta en casi exactamente 790 millones de duplicados en su prueba.

MacOS proporciona una función rand () no documentada en stdlib. Si lo deja sin sembrar, los primeros valores que genera son 16807, 282475249, 1622650073, 984943658 y 1144108930. Una búsqueda rápida mostrará que esta secuencia corresponde a un generador de números aleatorios LCG muy básico que itera la siguiente fórmula:

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

Dado que el estado de este RNG se describe completamente por el valor de un solo entero de 32 bits, su período no es muy largo. Para ser precisos, se repite cada 2 ³¹ - 2 iteraciones, generando cada valor de 1 a 2 ³¹ - 2.

No creo que haya una implementación estándar de rand () para todas las versiones de Linux, pero hay una función glibc rand () que a menudo se usa. En lugar de una sola variable de estado de 32 bits, utiliza un conjunto de más de 1000 bits, que a todos los efectos nunca producirá una secuencia completamente repetida. De nuevo, probablemente pueda averiguar qué versión tiene imprimiendo los primeros resultados de este RNG sin enviarlo primero. (La función glibc rand () produce los números 1804289383, 846930886, 1681692777, 1714636915 y 1957747793.)

Entonces, la razón por la que está obteniendo más colisiones en Linux (y casi ninguna en MacOS) es que la versión Linux de rand () es básicamente más aleatoria.

rand()está definido por el estándar C, y el estándar C no especifica qué algoritmo usar. Obviamente, Apple está utilizando un algoritmo inferior a su implementación de GNU / Linux: el de Linux no se puede distinguir de una fuente aleatoria verdadera en su prueba, mientras que la implementación de Apple simplemente baraja los números.

Si desea números aleatorios de cualquier calidad, use un PRNG mejor que brinde al menos algunas garantías sobre la calidad de los números que devuelve, o simplemente lea /dev/urandomo similar. El último le proporciona números de calidad criptográfica, pero es lento. Incluso si es demasiado lento por sí solo, /dev/urandompuede proporcionar algunas semillas excelentes a otro PRNG más rápido.

En general, el par rand / srand se ha considerado como obsoleto durante mucho tiempo debido a que los bits de bajo orden muestran menos aleatoriedad que los bits de alto orden en los resultados. Esto puede o no tener algo que ver con sus resultados, pero creo que esta es una buena oportunidad para recordar que a pesar de que algunas implementaciones rand / srand ahora están más actualizadas, las implementaciones más antiguas persisten y es mejor usarlas al azar (3 ) En mi cuadro Arch Linux, la siguiente nota todavía está en la página de manual 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.)

Justo debajo de eso, la página de manual en realidad ofrece implementaciones de ejemplo muy breves y muy simples de rand y srand que tratan sobre los RNG de LC más simples que hayas visto y que tienen un pequeño RAND_MAX. No creo que coincidan con lo que hay en la biblioteca estándar de C, si alguna vez lo hicieron. O al menos eso espero.

En general, si va a usar algo de la biblioteca estándar, use aleatorio si puede (la página del manual lo enumera como estándar POSIX de regreso a POSIX.1-2001, pero rand es estándar mucho antes de que C fuera incluso estandarizado) . O mejor aún, abra las Recetas Numéricas (o búsquelas en línea) o Knuth e implemente una. Son realmente fáciles y solo necesita hacerlo una vez para tener un RNG de propósito general con los atributos que necesita con mayor frecuencia y que es de calidad conocida.