direita|miniaturadaimagem| Gráfico tridimensional de 100.000 valores gerados com RANDU . Cada ponto representa 3 valores pseudoaleatórios consecutivos. É claramente visto que os pontos estão em 15 planos bidimensionais . O teste espectral é um teste estatístico para verificação da qualidade das classes de geradores de números pseudoaleatórios (PRNGs), os geradores congruenciais lineares (LCGs).. Os LCGs têm uma propriedade que, quando plotados em 2 ou mais dimensões, formam linhas ou hiperplanos, nos quais todas as saídas possíveis podem ser encontradas. O teste espectral compara a distância entre esses planos; quanto mais distantes eles estiverem, pior será o gerador. Como este teste foi desenvolvido para estudar as estruturas reticulares de LCGs, ele não pode ser aplicado a outras famílias de PRNGs.

De acordo com Donald Knuth,. this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM subroutine RANDUIBM, System/360 Scientific Subroutine Package, Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.

o LCG falha neste teste para valores maiores que 3 dimensões.

O primeiro passo é a geração de uma sequência utilizando-se o PRNG escolhido. Seja a separação máxima entre os planos paralelos de cobertura da sequência . O teste espectral verifica se a sequência não se degrada muito rapidamente.

Knuth aconselha verificar se cada um dos 5 números a seguir é > 0,01. onde é o módulo do LCG.

Números de mérito Knuth define um número de mérito, que é um valor que descreve quão próxima é a separação do mínimo teórico. Sob a re-notação de Steele & Vigna, para a dimensão , a figura é definida como Associated software and data at https://github.com/vigna/CPRNG. onde são definidos como antes, e é a constante de Hermite de dimensão d . é a menor separação interplanar possível.

L'Ecuyer (1991) introduziu ainda duas métricas correspondendo ao mínimo de em várias dimensões. Be sure to read the Errata as well. Novamente sob re-notação, é o mínimo para um LCG de dimensões 2 a , e é o mesmo para um gerador de números pseudoaleatórios congruentes multiplicativos (MCG), ou seja, um onde apenas a multiplicação é usada, ou que . Steele e Vigna observam que o é calculado de forma diferente nestes dois casos, necessitando de valores separados. Eles definem ainda uma média ponderada de mérito “harmônica”, (e ).

Exemplos Uma pequena variante do algoritmo RANDU, com tem: d 2 3 4 5 6 7 8 ν 536936458 118 116 116 116 μd​ 3.14 10 −5 10 −4 10 −3 0,02 fd 0,520224 0,018902 0,084143 0,207185 0,368841 0,552205 0,578329 Os números agregados de mérito são: , .

George Marsaglia (1972) considerava como "um candidato ao melhor de todos os multiplicadores" porque é fácil de lembrar e tem números de teste espectrais particularmente grandes. d 2 3 4 5 6 7 8 ν 4243209856 2072544 52804 6990 242 μd 3.10 2,91 3.20 5.01 0,017 fd 0,462490 0,313127 0,457183 0,552916 0,376706 0,496687 0,685247 Os números agregados de mérito são: , .

Steele & Vigna (2020) fornecem os multiplicadores com os maiores números agregados de mérito para muitas escolhas de m = 2n e um determinado comprimento de bit de a . Eles também fornecem os valores e um pacote de software para calcular esses valores. Por exemplo, eles relatam que o melhor a de 17 bits para m = 232 é:

Para um LCG (c ≠ 0), (121525). , . Para um MCG (c = 0), (125229). , .

Ilustração adicional

Notas

Leitura adicional – lista (anotado como neste texto) de muitos LCGs conhecidos Uma versão expandida desse trabalho está disponível como:

Categoria:Testes estatísticos