sudafricano - ¿Por qué se usa 1103515245 en rand?
rand sudafricano a dolar (4)
Ese número parece especial, es solo entre dos números primos: P.
Ahora hablando en serio, para ver si es una buena opción, solo mira la salida. Debería ver resultados muy diferentes, incluso si voltea un solo bit.
Además, tenga en cuenta la previsibilidad que espera ... que la implementación es terrible, puede considerar una alternativa más robusta pero simple, como FNV-1a .
Estoy hablando de this implementación sorprendentemente simple de rand() del estándar C:
static unsigned long int next = 1;
int rand(void) /* RAND_MAX assumed to be 32767. */
{
next = next * 1103515245 + 12345;
return (unsigned)(next/65536) % 32768;
}
De este artículo de Wikipedia sabemos que el multiplicador a (en el código anterior a = 1103515245 ) debería cumplir solo 2 condiciones:
-
a - 1es divisible por todos los factores primos dem.
(En nuestro casom = 2^32, tamaño de la int, entoncesmtiene solo un factor principal = 2) -
a - 1es un múltiplo de 4 simes un múltiplo de 4.
(32768 es múltiplo de 4 y 1103515244 también)
¿Por qué han elegido un número tan extraño, difícil de recordar, "hombre, estoy harto de estos números aleatorios, escriba lo que sea", como 1103515245?
Tal vez hay algunas razones sabias, que este número es de alguna manera mejor que el otro?
Por ejemplo, ¿por qué no establecer a = 20000000001 ? Es más grande, atractivo y fácil de recordar.
Los primeros cálculos tendían a preocuparse por los bits y bytes y jugaban trucos con los registros para minimizar los bytes de código (antes de las líneas había bytes)
Solo he encontrado una pista razonable a continuación:
La salida de este generador no es muy aleatoria. Si utilizamos el generador de muestras mencionado anteriormente, entonces la secuencia de 16 bytes clave será altamente no aleatoria. Por ejemplo, resulta que el bit bajo de cada salida sucesiva de rand () se alternará (por ejemplo, 0,1,0,1,0,1, ...). ¿Ves por qué? El bit bajo de x * 1103515245 es el mismo que el bit bajo de xy luego, al agregar 12345 solo se voltea el bit bajo. Por lo tanto, el bit bajo se alterna. Esto reduce el conjunto de claves posibles a solo 2113 posibilidades, mucho menos que el valor deseado de 2128.
http://inst.eecs.berkeley.edu/~cs161/fa08/Notes/random.pdf
Y dos respuestas razonables:
Mejora de un generador de números aleatorios pobres (1976) por Bays, Durham Bays, Carter, SD Durham
Recuerde que rand() es una aproximación de una distribución uniforme . Esos números se utilizan porque se han probado para mostrar que generan una distribución de aspecto más uniforme.
Dada la multitud de pares de enteros sin signo en el rango representable, dudo que alguien los haya probado todos con todas las semillas válidas. Si crees que tienes una mejor opción de parámetros, ¡pruébalo! Tienes el código, solo factoriza los parámetros del LCG y ejecuta pruebas. Genere un grupo de números (digamos 10 millones), calcule un histograma de los números generados y trace eso para ver la distribución.
editar Si está interesado en desarrollar un generador de números pseudoaleatorios para usar en aplicaciones reales, le recomiendo que lea sobre la considerable literatura sobre el tema. El "consejo" dado anteriormente solo se sugiere para ayudar a mostrar que la elección de parámetros LCG arbitrarios "más grandes, de aspecto fresco y más fáciles de recordar" dará una distribución muy pobre. /editar
Además, es una función de biblioteca y nunca he visto un programa que use la versión de biblioteca estándar de rand() para recordar los parámetros de su LCG.
Si usa un LCG para dibujar puntos en el espacio didimensional, se colocará a lo sumo (d! M) 1 / d de hiperplanos. Este es un defecto conocido de los LCG.
Si no eliges cuidadosamente a y m (más allá de la condición de periodicidad completa), pueden estar en muchos menos aviones que eso. Esos números han sido seleccionados por lo que se llama la prueba espectral .
La "prueba espectral" (el nombre proviene de la teoría de números) es la distancia máxima entre hiperplanos consecutivos en los que se encuentran las distribuciones de las articulaciones d-dimensionales. Desea que sea lo más pequeño posible durante todos los días que pueda probar.
Vea este documento para una revisión histórica sobre el tema. Tenga en cuenta que el generador que cita se menciona en el documento (como ANSIC) y se determina que no es muy bueno. Sin embargo, los 16 bits de orden superior son aceptables, pero muchas aplicaciones necesitarán más de 32768 valores distintos (como usted señala en los comentarios, el período es de hecho 2 ^ 31 - las condiciones para la periodicidad completa en el enlace de Wikipedia probablemente solo sean necesarias )
El código fuente original en el documento ANSI no tomó el orden más alto de 16 bits, produciendo un generador muy pobre que es fácil de usar incorrectamente ( rand() % n es lo que la gente piensa primero para dibujar un número entre 0 y n , y esto produce algo muy no aleatorio en este caso).
Ver también la discusión sobre los LCG en Recetas Numéricas. Citando:
Peor aún, muchos generadores tempranos hicieron elecciones particularmente malas para m y a. Una de esas rutinas infames, RANDU, con a = 65539 ym = 231, se extendió por los ordenadores centrales de IBM durante muchos años y se copió ampliamente en otros sistemas. Uno de nosotros recuerda como un estudiante graduado que produce una trama "aleatoria" con solo 11 aviones y el consultor de programación de su centro informático le dijo que había utilizado mal el generador de números aleatorios: "Garantizamos que cada número es aleatorio individualmente, pero no lo hacemos". Garantizar que más de uno de ellos sea aleatorio ". ¡Eso retrasó nuestra educación de postgrado por al menos un año!