RANDU [1] es un generador de números pseudoaleatorios (LCG) congruencial lineal del tipo Park-Miller , que se ha utilizado desde la década de 1960. [2] Se define por la recurrencia :
con el número de semilla inicial, como un número impar . Genera enteros pseudoaleatorios que se distribuyen uniformemente en el intervalo [1, 2 31 - 1] , pero en aplicaciones prácticas a menudo se mapean en racionales pseudoaleatorios en el intervalo (0, 1) , por la fórmula:
- .
RANDU de IBM es ampliamente considerado como uno de los generadores de números aleatorios más mal concebidos jamás diseñado, [3] y fue descrito como "verdaderamente horrible" por Donald Knuth . [4] No pasa mal la prueba espectral para dimensiones superiores a 2, y cada resultado entero es impar. Sin embargo, al menos ocho bits de orden inferior se eliminan cuando se convierten a punto flotante de precisión simple (mantisa de 32 bits y 24 bits).
La razón para elegir estos valores particulares es que con un tamaño de palabra entero de 32 bits, la aritmética de mod 2 31 y los cálculos se pueden hacer rápidamente, utilizando características especiales de algunos equipos informáticos.
Problemas con el multiplicador y el módulo.
En general, cuando se utiliza un LCG con módulo 2 31 para producir puntos (x k , x k + 1 , x k + 2 ) en un espacio tridimensional, los puntos caen en no más de 2344 planos paralelos, [5] a resultado que indica que un LCG no es adecuado para la simulación Monte Carlo . La elección del multiplicador determina el número de planos. Para mostrar el problema con los valores del multiplicador 65539 y módulo 2 31 elegidos para RANDU, considere el siguiente cálculo donde cada término debe tomarse como módulo 2 31 . Comience escribiendo la relación recursiva como:
que se convierte, después de expandir el factor cuadrático:
- porque 2 32 mod 2 31 = 0
y nos permite mostrar la correlación entre tres puntos como:
Como resultado de esta correlación, cada punto se encuentra en uno de un conjunto de planos paralelos separados por 2 31 , 15 de los cuales intersecan el cubo de 2 31 x 2 31 x 2 31 que contiene los puntos. Como resultado del amplio uso de RANDU a principios de la década de 1970, muchos resultados de esa época se consideran sospechosos. [6]
Este mal comportamiento ya fue detectado en 1963 [7] en una computadora de 36 bits, y cuidadosamente reimplementado [ aclaración necesaria ] en el IBM System / 360 de 32 bits . Se creía que había sido ampliamente depurado a principios de la década de 1990 [8], pero todavía había compiladores de FORTRAN usándolo hasta 1999. [1]
Salida de muestra
El inicio del período de salida de RANDU para la semilla inicial es:
Referencias
- ^ a b Manual de referencia del lenguaje Compaq Fortran (Número de pedido: AA-Q66SD-TK) Septiembre de 1999 (anteriormente DIGITAL Fortran y DEC Fortran 90)
- ^ Entacher, Karl (junio de 2000). "Una colección de generadores de números pseudoaleatorios clásicos con estructuras lineales - versión avanzada" . Archivado desde el original el 18 de noviembre de 2018.
- ^ Knuth DE El arte de la programación informática , volumen 2: algoritmos seminuméricos , segunda edición. Addison-Wesley, 1981. ISBN 0-201-03822-6 . Sección 3.3.4, p. 104. "¡Su mismo nombre RANDU es suficiente para provocar consternación en los ojos y el estómago de muchos informáticos!" [Amplia cobertura de pruebas estadísticas de no aleatoriedad.]
- ^ Knuth (1998), p. 188
- ^ Marsaglia, George (1968). "Los números aleatorios caen principalmente en los planos" . Proc. Natl. Acad. Sci. USA . 61 (1): 25-28. doi : 10.1073 / pnas.61.1.25 . PMC 285899 . PMID 16591687 .
- ^ Prensa, William H .; et al. (1992). Recetas numéricas en Fortran 77: El arte de la informática científica (2ª ed.). ISBN 0-521-43064-X.
- ^ ref. 7 de http://portal.acm.org/citation.cfm?id=363827
- ^ Entrevista con Donald Knuth