Wichmann–Hill

Wichmann–Hill es un generador de números pseudoaleatorios propuesto en 1982 por Brian Wichmann y David Hill. ^[1] Consiste en tres generadores congruenciales lineales con diferentes módulos primos , cada uno de los cuales se utiliza para producir un número distribuido uniformemente entre 0 y 1. Estos se suman, módulo 1, para producir el resultado. ^[2]

La suma de tres generadores produce una secuencia pseudoaleatoria con un ciclo superior6,95 × 10 ¹² . ^[3] Específicamente, los módulos son 30269, 30307 y 30323, produciendo períodos de 30268, 30306 y 30322. El período general es el mínimo común múltiplo de estos: 30268×30306×30322/4 =6 953 607 871 644. Esto ha sido confirmado por una búsqueda de fuerza bruta . ^{[4] [5]}

Implementación

El siguiente pseudocódigo es para su implementación en máquinas capaces de realizar operaciones aritméticas con números enteros de hasta5.212.632 :

[r, s1, s2, s3] = function ( s1 , s2 , s3 ) es  // s1, s2, s3 deben ser aleatorios de 1 a 30 000. Use el reloj si está disponible.  s1  := mod(171 × s1 , 30269) s2  := mod(172 × s2 , 30307) s3  := mod(170 × s3 , 30323) r  := modificación( s1 /30269.0 + s2 /30307.0 + s3 /30323.0, 1)

Para máquinas limitadas a números enteros con signo de 16 bits, el siguiente código equivalente solo usa números de hasta30,323 :

[r, s1, s2, s3] = function ( s1 , s2 , s3 ) es  // s1, s2, s3 deben ser aleatorios de 1 a 30 000. Use el reloj si está disponible.  s1  := 171 × mod( s1 , 177) − 2 × floor( s1 / 177) s2  := 172 × mod( s2 , 176) − 35 × floor( s2 / 176) s3  := 170 × mod( s3 , 178) − 63 × floor( s3 / 178) r  := mod(s1/30269 + s2/30307 + s3/30323, 1)

Los valores de semilla s1y deben inicializarse con valores distintos de cero s2.s3

Referencias

1. Wichmann, Brian A.; Hill, I. David (1982). "Algoritmo AS 183: un generador de números pseudoaleatorios eficiente y portátil". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 31 (2): 188–190. doi :10.2307/2347988. JSTOR  2347988.
2. McLeod, A. Ian (1985). "Remark AS R58: A Remark on Algorithm AS 183. An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Serie C (Estadística Aplicada) . 34 (2): 198–200. doi :10.2307/2347378. JSTOR  2347378. Wichmann y Hill (1982) afirman que su generador RANDOM producirá números pseudoaleatorios uniformes que son estrictamente mayores que cero y menores que uno. Sin embargo, dependiendo de la precisión de la máquina, se pueden producir algunos valores cero debido a un error de redondeo. El problema ocurre con el punto flotante de precisión simple al redondear a cero.
3. Wichmann, Brian; Hill, David (1984). "Corrección: Algoritmo AS 183: Un generador de números pseudoaleatorios eficiente y portátil". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 33 (1): 123. doi :10.2307/2347676. JSTOR  2347676.
4. Rikitake, Kenji (16 de marzo de 2017). "Calculadora de estado interno del algoritmo AS183 PRNG en C". GitHub .
5. Zeisel, H. (1986). "Remark ASR 61: A Remark on Algorithm AS 183. An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Series C (Estadística Aplicada) . 35 (1): 98. doi :10.1111/j.1467-9876.1986.tb01945.x. JSTOR  2347876. Wichmann y Hill (1982) sugirieron un generador pseudoaleatorio basado en la suma de números pseudoaleatorios generados por métodos congruenciales multiplicativos. Sin embargo, esto no es más que un método eficiente para implementar un generador congruencial multiplicativo con una longitud de ciclo mucho mayor que el entero máximo. Utilizando el Teorema del Resto Chino (ver por ejemplo Knuth, 1981 ) puedes probar que obtendrás los mismos resultados utilizando sólo un generador congruencial multiplicativo X _{n +1} = α ⋅ X _n módulo m con α = 1655 54252 64690 , m = 2781 71856 04309 . Sin embargo, la versión original todavía es necesaria para hacer que un generador con constantes tan largas funcione en aritmética informática ordinaria.