Wichmann – Hill es un generador de números pseudoaleatorios propuesto en 1982 por Brian Wichmann y David Hill. [1] Consta de 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 que excede 6,95 × 10 12 . [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 implementación en máquinas capaces de aritmética de enteros hasta5 212 632 :
[r, s1, s2, s3] = función ( s1 , s2 , s3 ) es // s1, s2, s3 debe ser aleatorio de 1 a 30.000. Utilice el reloj si está disponible. s1 : = mod (171 × s1 , 30269) s2 : = mod (172 × s2 , 30307) s3 : = mod (170 × s3 , 30323) r : = mod ( s1 /30269.0 + s2 /30307.0 + s3 /30323.0, 1)
Para máquinas limitadas a enteros de 16 bits con signo, el siguiente código equivalente solo usa números hasta 30,323:
[r, s1, s2, s3] = función ( s1 , s2 , s3 ) es // s1, s2, s3 debe ser aleatorio de 1 a 30.000. Utilice el reloj si está disponible. s1 : = 171 × mod ( s1 , 177) - 2 × piso ( s1 / 177) s2 : = 172 × mod ( s2 , 176) - 35 × piso ( s2 / 176) s3 : = 170 × mod ( s3 , 178) ) - 63 × piso ( s3 / 178) r : = mod (s1 / 30269 + s2 / 30307 + s3 / 30323, 1)
Los valores de semilla s1
, s2
y s3
deben ser inicializadas a valores distintos de cero.
Referencias
- ^ Wichmann, Brian A .; Hill, I. David (1982). "Algoritmo como 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 .
- ^ McLeod, A. Ian (1985). "Observación como R58: una observación sobre el algoritmo AS 183. Un generador de números pseudoaleatorios eficiente y portátil". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 34 (2): 198-200. doi : 10.2307 / 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, pueden producirse algunos valores cero debido a un error de redondeo.
El problema ocurre con el punto flotante de precisión simple cuando se redondea a cero. - ^ 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 .
- ^ Rikitake, Kenji. "Calculadora de estado interno del algoritmo AS183 PRNG en C" .
- ^ Zeisel, H. (1986). "Observación ASR 61: una observación sobre el algoritmo AS 183. Un generador de números pseudoaleatorios eficiente y portátil". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 35 (1): 98. doi : 10.2307 / 2347676 .
Wichmann y Hill (1982) sugirieron un generador pseudoaleatorio basado en la suma de números pseudoaleatorios basado en la suma de números pseudoaleatorios generados por métodos congruentes multiplicativos. Sin embargo, esto no es más que un método eficiente para implementar un generador congruencial multiplicativo con una duración de ciclo mucho mayor que el número entero máximo. Usando el teorema chino del residuo (ver, por ejemplo , Knuth, 1981 ), puede demostrar que obtendrá los mismos resultados usando solo un generador congruencial multiplicativo X n +1 = α ⋅ X n módulo m con α = 1655 54252 64690 , m = 2781 71856 04309 . La versión original, sin embargo, todavía es necesaria para hacer que un generador con constantes tan largas funcione en la aritmética de computadora ordinaria.