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 (módulo 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 un estándar implementación 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.
Si bien al principio puede sonar como 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-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. Así que Linux rand() la implementación es en esta prueba indistinguible 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 manejar para 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 de nuevo. 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 desde que existe macOS (u OS X), por lo que la calidad de rand() probablemente no se considere importante, y simplemente se quedaron 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.
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 algunas semillas excelentes a algún otro PRNG más rápido.
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 incluso 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 reconocida.