RANDU

RANDU ^{[ 1 ]} es un método obsoleto para generar números aleatorios utilizado principalmente en las décadas de 1960 y 1970. ^{[ 2 ]} Es un generador congruencial lineal (LCG) del tipo Park-Miller ^{[ 2 ]} definido por la recurrencia

${\displaystyle V_{j+1}=65539\cdot V_{j}{\bmod {2}}^{31}}$

con el número de semilla inicial${\displaystyle V_{0}}$como un número impar . Genera números enteros pseudoaleatorios.${\displaystyle V_{j}}$que se distribuyen uniformemente en el intervalo [0, 2 ³¹ − 1] , pero en aplicaciones prácticas a menudo se transforman en racionales pseudoaleatorios.${\displaystyle X_{j}}$en el intervalo (0, 1) , por la fórmula

${\displaystyle X_{j}={\frac {V_{j}}{2^{31}}}.}$

RANDU de IBM es ampliamente considerado como uno de los generadores de números aleatorios peor concebidos jamás diseñados, ^{[ 3 ]} y fue descrito como "verdaderamente horrible" por Donald Knuth . ^{[ 4 ]} Falla estrepitosamente la prueba espectral para dimensiones mayores que 2, como se muestra a continuación.

La razón para elegir estos valores particulares para el multiplicador y el módulo fue que con un tamaño de palabra entera de 32 bits, la aritmética de mod 2 ³¹ y${\displaystyle 65539=2^{16}+3}$Los cálculos podían realizarse rápidamente utilizando operadores bit a bit en el hardware, pero los valores se eligieron por conveniencia computacional, no por su calidad estadística.

Para cualquier generador congruencial lineal con módulo m utilizado para generar puntos en un espacio n -dimensional, los puntos caen en no más de${\displaystyle (n!\times m)^{1/n}}$hiperplanos paralelos. ^{[ 5 ]} Esto indica que los LCG de módulo bajo no son adecuados para la simulación de Monte Carlo de alta dimensión . Para m = 2 ³¹ y n = 3, un LCG podría tener hasta 2344 planos, máximo teórico. En el mismo artículo de Marsaglia se demuestra un límite superior mucho más ajustado como la suma de los valores absolutos de todos los coeficientes de los hiperplanos en forma estándar. Es decir, si los hiperplanos son de la forma Ax ₁ + Bx ₂ + Cx ₃ = algún entero como 0, 1, 2, etc., entonces el número máximo de planos es | A | + | B | + | C |. ^{[ 5 ]}

Ahora examinamos los valores del multiplicador 65539 y del módulo 2 ³¹ elegidos para RANDU. Consideremos el siguiente cálculo donde cada término debe tomarse módulo 2 ^31. Comencemos escribiendo la relación recursiva como

${\displaystyle x_{k+2}=(2^{16}+3)x_{k+1}=(2^{16}+3)^{2}x_{k},}$

que después de expandir el factor cuadrático se convierte en

${\displaystyle x_{k+2}=(2^{32}+6\cdot 2^{16}+9)x_{k}=[6\cdot (2^{16}+3)-9]x_{k}}$

(porque 2 ³² mod 2 ³¹ = 0 ) y nos permite mostrar la correlación entre tres puntos como

${\displaystyle x_{k+2}=6x_{k+1}-9x_{k}.}$

Sumando los valores absolutos de los coeficientes, obtenemos no más de 16 planos en 3D, que se convierten en solo 15 planos al examinarlos más de cerca, como se muestra en el diagrama anterior. Incluso para los estándares de los LCG, esto demuestra que RANDU es terrible: usar RANDU para muestrear un cubo unitario solo muestreará 15 planos paralelos, ni siquiera cerca del límite superior de${\displaystyle {\Big \lfloor }{\big (}2^{31}\times 3!{\big )}^{1/3}{\Big \rfloor }=2344}$aviones.

Como resultado del uso generalizado de RANDU a principios de la década de 1970, muchos resultados de esa época se consideran sospechosos. ^{[ 6 ]} Este comportamiento anómalo ya se había detectado en 1963 ^{[ 7 ]} en un ordenador de 36 bits y se reimplementó cuidadosamente en el IBM System/360 de 32 bits . Se creía que se había eliminado en gran medida a principios de la década de 1990 ^{[ 8 ]} , pero todavía había compiladores de FORTRAN que lo utilizaban hasta 1999. ^{[ 1 ]}

El inicio del período de producción de RANDU para la semilla inicial${\displaystyle V_{0}=1}$es

1, 65539, 393225, 1769499, 7077969, 26542323, … (secuencia A096555 en el OEIS ) .

• Citas relacionadas con RANDU en Wikiquote