Prueba espectral

La prueba espectral es una prueba estadística para evaluar la calidad de una clase de generadores de números pseudoaleatorios (GNA), los generadores congruenciales lineales (GCL). ^{[ 1 ]} Los GCL tienen la propiedad de que, al representarlos en dos o más dimensiones, se forman líneas o hiperplanos en los que se pueden encontrar todas las salidas posibles. ^{[ 2 ]} La prueba espectral compara la distancia entre estos planos; cuanto mayor sea la distancia entre ellos, peor será el generador. ^{[ 3 ]} Dado que esta prueba está diseñada para estudiar las estructuras reticulares de los GCL, no puede aplicarse a otras familias de GNA.

Según Donald Knuth , ^{[ 4 ]} esta es, con mucho, la prueba más potente conocida, porque puede hacer fallar a LCG que pasan la mayoría de las pruebas estadísticas. La subrutina RANDU de IBM ^{[ 5 ] [ 6 ]} LCG falla en esta prueba para 3 dimensiones o más.

Dejemos que el generador de números pseudoaleatorios genere una secuencia . Sea la separación máxima entre planos paralelos que cubren la secuencia . La prueba espectral verifica que la secuencia no decaiga demasiado rápido.${\ Displaystyle u_ {1}, u_ {2}, \ puntos}$${\displaystyle 1/\nu _{t}}$${\displaystyle \{(u_{n+1:n+t})\mid n=0,1,\dots \}}$${\displaystyle \nu _{2},\nu _{3},\nu _{4},\dots }$

Knuth recomienda comprobar que cada uno de los siguientes 5 números sea mayor que 0,01, donde es el módulo del LCG.$${\displaystyle {\begin{aligned}\mu _{2}&=\pi \nu _{2}^{2}/m,&\mu _{3}&={\frac {4}{3}}\pi \nu _{3}^{3}/m,&\mu _{4}&={\frac {1}{2}}\pi ^{2}\nu _{4}^{4}/m,\\[1ex]&&\mu _{5}&={\frac {8}{15}}\pi ^{2}\nu _{5}^{5}/m,&\mu _{6}&={\frac {1}{6}}\pi ^{3}\nu _{6}^{6}/m,\end{aligned}}}$$${\displaystyle m}$

Knuth define una figura de mérito que describe cuán cerca está la separación del mínimo teórico. Bajo la renotación de Steele y Vigna, para una dimensión , la figura se define como ^{[ 7 ] : 3} donde se definen como antes, y es la constante de Hermite de dimensión d . es la separación interplanar más pequeña posible. ^{[ 7 ] : 3}${\displaystyle 1/\nu _{t}}$${\displaystyle d}$${\displaystyle f_{d}}$$${\displaystyle f_{d}(m,a)=\nu _{d}/\left(\gamma _{d}^{1/2}{\sqrt[{d}]{m}}\right),}$$${\displaystyle a,m,\nu _{d}}$${\displaystyle \gamma _{d}}$${\displaystyle \gamma _{d}^{1/2}{\sqrt[{d}]{m}}}$

L'Ecuyer 1991 introduce además dos medidas correspondientes al mínimo de en varias dimensiones. ^{[ 8 ]} Nuevamente bajo una nueva notación, es el mínimo para un LCG de dimensiones 2 a , y es el mismo para un generador de números pseudoaleatorios congruenciales multiplicativos (MCG), es decir, uno donde solo se usa la multiplicación, o . Steele y Vigna señalan que se calcula de manera diferente en estos dos casos, lo que requiere valores separados. ^{[ 7 ] : 13} Además definen una figura de mérito promedio ponderada "armónica" , (y ). ^{[ 7 ] : 13}${\displaystyle f_{d}}$${\displaystyle {\mathcal {M}}_{d}^{+}(m,a)}$${\displaystyle f_{d}}$${\displaystyle d}$${\displaystyle {\mathcal {M}}_{d}^{*}(m,a)}$${\displaystyle c=0}$${\displaystyle f_{d}}$${\displaystyle {\mathcal {H}}_{d}^{+}(m,a)}$${\displaystyle {\mathcal {H}}_{d}^{*}(m,a)}$

Una pequeña variante del infame RANDU , con : ^{[ 4 ] : (Tabla 1)}${\displaystyle x_{n+1}=65539\,x_{n}{\bmod {2}}^{29}}$

Las cifras agregadas de mérito son: , . ^{[ a ]}${\displaystyle {\mathcal {M}}_{8}^{*}(65539,2^{29})=0.018902}$${\displaystyle {\mathcal {H}}_{8}^{*}(65539,2^{29})=0.330886}$

George Marsaglia (1972) lo considera "un candidato para el mejor de todos los multiplicadores" porque es fácil de recordar y tiene números de prueba espectrales particularmente grandes. ^{[ 9 ]}${\displaystyle x_{n+1}=69069\,x_{n}{\bmod {2}}^{32}}$

Las cifras agregadas de mérito son: , . ^{[ a ]}${\displaystyle {\mathcal {M}}_{8}^{*}(69069,2^{32})=0.313127}$${\displaystyle {\mathcal {H}}_{8}^{*}(69069,2^{32})=0.449578}$

Steele y Vigna (2020) proporcionan los multiplicadores con las mayores cifras de mérito agregadas para muchas opciones de m = 2 ⁿ y una longitud de bits dada de a . También proporcionan los valores individuales y un paquete de software para calcular estos valores. ^{[ 7 ] : 14–5} Por ejemplo, informan que el mejor a de 17 bits para m = 2 ³² es:${\displaystyle f_{d}}$

• Para un LCG (c ≠ 0), 0x1dab5 (121525). , . ^{[ 7 ] : 14}${\displaystyle {\mathcal {M}}_{8}^{+}=0.6403}$${\displaystyle {\mathcal {H}}_{8}^{+}=0.6588}$
• Para un MCG (c = 0), 0x1e92d (125229). , . ^{[ 7 ] : 14}${\displaystyle {\mathcal {M}}_{8}^{*}=0.6623}$${\displaystyle {\mathcal {H}}_{8}^{*}=0.7497}$

• Entacher, Karl (enero de 1998). "Subsecuencias erróneas de generadores de números pseudoaleatorios congruenciales lineales bien conocidos". ACM Transactions on Modeling and Computer Simulation . 8 (1): 61– 70. doi : 10.1145/272991.273009 .– enumera (anotado como en este texto) muchos LCG conocidos ${\displaystyle f_{d}}$${\displaystyle S_{s}}$
  • Una versión ampliada de este trabajo está disponible como: Entacher, Karl (2001). "Una colección de generadores de números pseudoaleatorios seleccionados con estructuras lineales - versión ampliada" .