Estaba implementando un hashmap en C como parte de un proyecto en el que estoy trabajando y usando inserciones aleatorias para probarlo. Noté que rand() en Linux parece repetir números con mucha más frecuencia que en Mac. RAND_MAX es 2147483647/0x7FFFFFFF en ambas plataformas. Lo reduje a este programa de prueba que hace que una matriz de bytes RAND_MAX+1 sea larga, genera números aleatorios RAND_MAX , observa si cada uno es un duplicado y lo marca 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 siempre genera solo uno, por lo que recorre todos los números aleatorios que puede generar casi sin repetirlos. ¿Alguien puede explicarme cómo funciona esto? No puedo decir nada diferente de las páginas de man , no puedo decir qué RNG está usando cada uno y no puedo encontrar nada en línea. ¡Gracias!
rand() está definido por el estándar C, y el estándar C no especifica qué algoritmo usar. Obviamente, Apple está usando un algoritmo inferior a su implementación de GNU/Linux: el de Linux es indistinguible de una verdadera fuente aleatoria en su prueba, mientras que la implementación de Apple simplemente mezcla los números.
Si desea números aleatorios de cualquier calidad, use un PRNG mejor que ofrezca al menos algunas garantías sobre la calidad de los números que devuelve, o simplemente lea desde /dev/urandom o similar. El último te da números de calidad criptográfica, pero es lento. Incluso si es demasiado lento por sí mismo, /dev/urandom puede proporcionar excelentes semillas para algún otro PRNG más rápido.
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 norte +1 = 7 5 · x norte (mod 2 31 − 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 31 − 2 iteraciones, generando todos los valores de 1 a 2 31 − 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 se usa a menudo. En lugar de una sola variable de estado de 32 bits, esto utiliza un conjunto de más de 1000 bits, que para todos los efectos nunca producirá una secuencia completamente repetitiva. Una vez más, probablemente pueda averiguar qué versión tiene imprimiendo los primeros resultados de este RNG sin inicializarlo primero. (La función glibc rand() produce los números 1804289383, 846930886, 1681692777, 1714636915 y 1957747793).
Entonces, la razón por la que está teniendo más colisiones en Linux (y casi ninguna en MacOS) es que la versión de Linux de rand() es básicamente más aleatoria.
En general, el par rand/srand se ha considerado algo obsoleto durante mucho tiempo debido a que los bits de orden bajo muestran menos aleatoriedad que los bits de orden alto en los resultados. Esto puede o no tener nada que ver con sus resultados, pero creo que sigue siendo una buena oportunidad para recordar que aunque algunas implementaciones de rand/srand ahora están más actualizadas, las implementaciones más antiguas persisten y es mejor usar random(3 ). En mi caja de Arch Linux, la siguiente nota todavía está en la página del manual para 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 son los RNG LC más simples que jamás haya visto y que tienen un RAND_MAX pequeño. No creo que coincidan con lo que hay en la biblioteca estándar de C, si es que alguna vez lo hicieron. O al menos espero que no.
En general, si va a usar algo de la biblioteca estándar, use aleatorio si puede (la página de manual lo enumera como estándar POSIX desde POSIX.1-2001, pero rand es estándar mucho antes de que C fuera estandarizado) . O mejor aún, abra Numerical Recipes (o búsquelo en línea) o Knuth e implemente uno. Son realmente fáciles y solo necesita hacerlo una vez para tener un RNG de uso general con los atributos que necesita con más frecuencia y que es de calidad conocida.
Si bien al principio puede parecer que macOS rand() es de alguna manera mejor para no repetir ningún número, se 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 31 -1)/ e ). Del mismo modo, 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 implementación de Linux rand() es indistinguible en esta prueba de una verdadera fuente aleatoria, mientras que macOS rand() no lo es.
Otra cosa que parece sorprendente a primera vista es cómo macOS rand() puede evitar 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 y RAND_MAX , inclusive, exactamente una vez, antes de que la secuencia se repita nuevamente. Dado que 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 ves es el primero, y el 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 considere importante, y simplemente se han estancado. con uno de los generadores pseudoaleatorios más simples disponibles. (Como notó, su rand() incluso se comenta con una recomendación para usar arc4random() en su lugar).
En una nota relacionada, el generador de números pseudoaleatorios 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 da como resultado casi exactamente 790 millones de duplicados en su prueba.