Usuário:Marsjo.santos/Defesa Pirc

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 RANDU

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

O primeiro passo é a geração de uma sequência $u_{1},u_{2},\dots$ utilizando-se o PRNG escolhido. Seja $1/\nu _{t}$ a separação máxima entre os planos paralelos de cobertura da sequência $\{(u_{n+1:n+t})\mid n=0,1,\dots \}$ . O teste espectral verifica se a sequência $\nu _{2},\nu _{3},\nu _{4},\dots$ não se degrada muito rapidamente.

Knuth aconselha verificar se cada um dos 5 números a seguir é > 0,01. $${\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}}$$ onde $m$ é 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 $1/\nu _{t}$ do mínimo teórico. Sob a re-notação de Steele & Vigna, para a dimensão $d$, a figura $f_{d}$ é definida como$$f_{d}(m,a)=\nu _{d}/\left(\gamma _{d}^{1/2}{\sqrt[{d}]{m}}\right),$$ onde $a,m,\nu _{d}$ são definidos como antes, e $\gamma _{d}$ é a constante de Hermite de dimensão d . $\gamma _{d}^{1/2}{\sqrt[{d}]{m}}$ é a menor separação interplanar possível.

L'Ecuyer (1991) introduziu ainda duas métricas correspondendo ao mínimo de $f_{d}$ em várias dimensões. Novamente sob re-notação, ${\mathcal {M}}_{d}^{+}(m,a)$ é o mínimo $f_{d}$ para um LCG de dimensões 2 a $d$, e ${\mathcal {M}}_{d}^{*}(m,a)$ é o mesmo para um gerador de números pseudoaleatórios congruentes multiplicativos (MCG), ou seja, um onde apenas a multiplicação é usada, ou que $c=0$ . Steele e Vigna observam que o $f_{d}$ é calculado de forma diferente nestes dois casos, necessitando de valores separados.Eles definem ainda uma média ponderada de mérito “harmônica”, ${\mathcal {H}}_{d}^{+}(m,a)$ (e ${\mathcal {H}}_{d}^{*}(m,a)$ ).

Exemplos

Uma pequena variante do algoritmo RANDU, com $x_{n+1}=65539\,x_{n}{\bmod {2}}^{29}$ tem:

d	2	3	4	5	6	7	8
ν2 d	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: ${\mathcal {M}}_{8}^{*}(65539,2^{29})=0.018902$, ${\mathcal {H}}_{8}^{*}(65539,2^{29})=0.330886$.

George Marsaglia (1972) considerava $x_{n+1}=69069\,x_{n}{\bmod {2}}^{32}$ 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
ν 2 d	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: ${\mathcal {M}}_{8}^{*}(69069,2^{32})=0.313127$, ${\mathcal {H}}_{8}^{*}(69069,2^{32})=0.449578$.

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

• Para um LCG (c ≠ 0), (121525). ${\mathcal {M}}_{8}^{+}=0.6403$, ${\mathcal {H}}_{8}^{+}=0.6588$.
• Para um MCG (c = 0), (125229). ${\mathcal {M}}_{8}^{*}=0.6623$, ${\mathcal {H}}_{8}^{*}=0.7497$.

Ilustração adicional

Apesar do fato de ambas as relações passarem no Teste qui-quadrado, o primeiro LCG é menos aleatório que o segundo, pois o intervalo de valores que ele pode produzir pela ordem em que os produz é menos uniformemente distribuído.

Leitura adicional

• Entacher, Karl (janeiro 1998). «Bad subsequences of well-known linear congruential pseudorandom number generators». ACM Transactions on Modeling and Computer Simulation. 8 (1): 61–70. doi:10.1145/272991.273009  – lista $f_{d}$ (anotado como $S_{s}$ neste texto) de muitos LCGs conhecidos
  • Uma versão expandida desse trabalho está disponível como: Entacher, Karl (2001). «A Collection of Selected Pseudorandom Number Generators With Linear Structures - extended version» "A Collection of Selected Pseudorandom Number Generators With Linear Structures - extended version".

[[Categoria:Geradores de números pseudo-aleatórios]]