¿Por qué se usa 1103515245 en rand?

Question

Estoy hablando de this sorprendentemente simple aplicación de rand() de la norma 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 this Wikipedia article sabemos que el multiplicador a (en código a = 1103515245 arriba) debe cumplir con sólo 2 condiciones:

1. a - 1 es divisible por todos los factores primos de m.
   (En nuestro caso m = 2^32, el tamaño de la int, por lo m tiene sólo un factor primordial = 2)
2. a - 1 es un múltiplo de 4, si m es un múltiplo de 4.
   (32768 es múltiplo de 4, y 1103515244 demasiado)

por qué han elegido como una extraña, y difíciles de recordar, "hombre, yo estoy harto de estos números al azar, escribir lo que sea" número, 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.

Answer 1

Si utiliza un LCG para dibujar puntos en el espacio tridimensional d, van a estar en como máximo (d! M) ^/d hiperplanos. Este es un defecto conocido de los LCG.

Si no elige 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 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 articulaciones d-dimensionales. Desea que sea lo más pequeño posible durante todos los días que pueda probar.

Ver this paper 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ó la orden alto 16 bits, produciendo un generador muy pobre que es fácil de hacer mal uso (rand() % n es lo que la gente primero piensa en dibujar un número entre 0 y n, y esto produce algo muy no aleatorio en este caso).

Vea también la discusión sobre los LCG en Recetas Numéricas. Citando:

Peor aún, muchos generadores tempranos pasaron a ser particularmente malos elecciones para my 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 produciendo una trama "aleatoria" con solo 11 planos y el consultor de programación de su centro informático le dijo que había usado mal el generador de números aleatorios : "Garantizamos que cada número es aleatorio individualmente, pero no garantizamos que más de uno sea al azar. "¡Eso retrasó nuestra educación de postgrado por al menos un año!

Answer 2

Recuerde que rand() es una aproximación de uniform distribution. 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! Usted tiene el código, simplemente factorice los parámetros del LCG y ejecute 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.

edición Si usted está interesado en el desarrollo de un generador de números pseudo-aleatorios para su uso en aplicaciones reales, recomiendo que lea en la 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 utilizando la versión de la biblioteca estándar de rand() recordar parámetros de su LCG.

Answer 3

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 mire 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.

Answer 4

cálculos Los primeros tienden a preocuparse por los bits y bytes y trucos jugado con los registros de minimizar bytes de código (antes de las líneas había bytes)

sólo he encontrado debajo de una idea razonable:

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

http://en.wikipedia.org/wiki/TRNG