Mostrar código-fonte de Teste Espectral (estatística)

[[Imagem:Randu.png|direita|miniaturadaimagem| [[Espaço tridimensional|Gráfico tridimensional]] de 100.000 valores gerados com [[Algoritmo RANDU|RANDU]] . Cada ponto representa 3 valores pseudoaleatórios consecutivos. É claramente visto que os pontos estão em 15 [[Espaço bidimensional|planos]] bidimensionais .]]
O '''teste espectral''' é um teste estatístico para verificação da qualidade das classes de [[Gerador de números pseudoaleatórios|geradores de números pseudoaleatórios]] (PRNGs), os [[Geradores congruentes lineares|geradores congruenciais lineares]] (LCGs).<ref>{{Citation|último=Williams|primeiro1=K. B.|último2=Dwyer|primeiro2=Jerry|título=Testing Random Number Generators, Part 2|url=http://drdobbs.com/184403208|acessodata=26 de janeiro de 2012|data=1 de agosto de 1996|periódico=[[Dr. Dobb's Journal]]}}.</ref> 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.<ref name="Marsaglia68">{{Citar periódico |url=https://www.pnas.org/content/61/1/25.full.pdf |título=Random Numbers Fall Mainly in the Planes |data=setembro de 1968 |periódico=[[PNAS]] |número=1 |ultimo=Marsaglia |primeiro=George |autorlink=George Marsaglia |paginas=25–28 |bibcode=1968PNAS...61...25M |doi=10.1073/pnas.61.1.25 |pmc=285899 |pmid=16591687 |volume=61 |doi-access=free}}</ref> O teste espectral compara a distância entre esses planos; quanto mais distantes eles estiverem, pior será o gerador.<ref name="jain">{{Citar web|ultimo=Jain|primeiro=Raj|url=http://www.cse.wustl.edu/~jain/cse567-08/ftp/k_27trg.pdf|titulo=Testing Random-Number Generators (Lecture)|acessodata=2 de dezembro de 2016|website=[[Washington University in St. Louis]]}}</ref> 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]],<ref name=":0">{{Citation |último1=Knuth |primeiro1=Donald E. |título=[[The Art of Computer Programming]] volume 2: Seminumerical algorithms |ano=1981 |capítulo=3.3.4: The Spectral Test |edição=2nd |publicado=[[Addison-Wesley]] |autorlink1=Donald Knuth}}.</ref> this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM subroutine [[RANDU]]<ref name="ibm360">IBM, ''System/360 Scientific Subroutine Package,'' Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.</ref><ref name="ibmPackage">{{citar periódico
 |título=IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III
 |id=Scientific Application Program H20-0205-3
 |publicado=IBM Technical Publications Department
 |local=White Plains, NY
 |ano=1968
 |volume=II
 |doi=10.3247/SL2Soft08.001
 |página=77
 |url=http://www.ebyte.it/library/downloads/IBM_System360_SSP.pdf#page=81
|autor=((International Business Machines Corporation))
 |periódico=Stan's Library
 }}</ref>

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

O primeiro passo é a geração de uma sequência <math>u_1, u_2, \dots</math>  utilizando-se o PRNG escolhido. Seja <math>1/\nu_t</math> a separação máxima entre os planos paralelos de cobertura da sequência <math>\{(u_{n+1:n+t}) \mid n = 0, 1, \dots\}</math> . O teste espectral verifica se a sequência <math>\nu_2, \nu_3, \nu_4, \dots</math> não se degrada muito rapidamente.

Knuth aconselha verificar se cada um dos 5 números a seguir é > 0,01. <math display="block">
\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}
</math> onde <math>m</math> é 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 <math>1/\nu_t</math> do mínimo teórico. Sob a re-notação de Steele & Vigna, para a dimensão <math>d</math>, a figura <math>f_d</math> é definida como<ref name="Steele20">{{Citar periódico |url=https://www.researchgate.net/publication/354960552_Computationally_easy_spectrally_good_multipliers_for_congruential_pseudorandom_number_generators/fulltext/6155d14ae7bb415a5d438c07/Computationally-easy-spectrally-good-multipliers-for-congruential-pseudorandom-number-generators.pdf |título=Computationally easy, spectrally good multipliers for congruential pseudorandom number generators |data=fevereiro de 2022 |periódico=Software: Practice and Experience |número=2 |ultimo=Steele |primeiro=Guy L. Jr. |ultimo2=Vigna |primeiro2=Sebastiano |autorlink2=Sebastiano Vigna |paginas=443–458 |arxiv=2001.05304 |doi=10.1002/spe.3030 |volume=52 |doi-access=free}} Associated software and data at https://github.com/vigna/CPRNG.</ref>{{rp|3}}<math display="block">
 f_d(m, a) = \nu_d / \left(\gamma^{1/2}_d \sqrt[d]{m}\right),
</math> onde <math>a, m, \nu_d</math> são definidos como antes, e <math>\gamma_d</math> é a [[constante de Hermite]] de dimensão ''d'' . <math>\gamma^{1/2}_d \sqrt[d]{m}</math> é a menor separação interplanar possível.<ref name="Steele20" /> {{rp|3}}

L'Ecuyer (1991) introduziu ainda duas métricas correspondendo ao mínimo de <math>f_d</math> em várias dimensões.<ref name="LEcuyer99">{{Citar periódico |url=https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf |título=Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure |data=janeiro de 1999 |periódico=[[Mathematics of Computation]] |número=225 |ultimo=L'Ecuyer |primeiro=Pierre |paginas=249–260 |bibcode=1999MaCom..68..249L |citeseerx=10.1.1.34.1024 |doi=10.1090/S0025-5718-99-00996-5 |volume=68}}  Be sure to read the [https://www.iro.umontreal.ca/~lecuyer/myftp/papers/latrules99Errata.pdf Errata] as well.</ref> Novamente sob re-notação, <math>\mathcal{M}^+_d(m, a)</math> é o mínimo <math>f_d</math> para um LCG de dimensões 2 a <math>d</math>, e <math>\mathcal{M}^*_d(m, a)</math> é o mesmo para um gerador de números pseudoaleatórios congruentes multiplicativos (MCG), ou seja, um onde apenas a multiplicação é usada, ou que <math>c = 0</math> . Steele e Vigna observam que o <math>f_d</math> é calculado de forma diferente nestes dois casos, necessitando de valores separados.<ref name="Steele20"/> {{rp|13}}Eles definem ainda uma média ponderada de mérito “harmônica”, <math>\mathcal{H}^+_d(m, a)</math> (e <math>\mathcal{H}^*_d(m, a)</math> ).<ref name="Steele20" /> {{rp|13}}

== Exemplos ==
Uma pequena variante do algoritmo [[Algoritmo RANDU|RANDU]], com <math>x_{n+1} = 65539 \, x_n \bmod 2^{29}</math> tem:<ref name=":0"/> {{rp|em=Tabela 1}}
{| class="wikitable"
!''d''
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|-
! ''&#x3BD;''{{Su|p=2|b=''d''}}
| 536936458
| 118
| 116
| 116
| 116
|-
! ''&#x3BC;''<sub>''d''</sub>
| 3.14
| 10 <sup>−5</sup>
| 10 <sup>−4</sup>
| 10 <sup>−3</sup>
| 0,02
|-
! ''f''<sub>''d''</sub>{{nre|nome=SSSoft|Calculado usando o software de Steele & Vigna (2020), "mspect" (src/spect.cpp, modo multiplicativo).}}
| 0,520224
| 0,018902
| 0,084143
| 0,207185
| 0,368841
| 0,552205
| 0,578329
|}
Os números agregados de mérito são: <math>\mathcal{M}^{*}_8(65539, 2^{29}) = 0.018902</math>, <math>\mathcal{H}^{*}_8(65539, 2^{29}) = 0.330886</math>.{{nre|nome=SSSoft}}

[[George Marsaglia]] (1972) considerava <math>x_{n+1} = 69069 \, x_n \bmod 2^{32}</math> como "um candidato ao melhor de todos os multiplicadores" porque é fácil de lembrar e tem números de teste espectrais particularmente grandes.<ref name="marsaglia72">{{Citation|último=Marsaglia|primeiro1=GEORGE|título=The Structure of Linear Congruential Sequences|data=1972-01-01|periódico=Applications of Number Theory to Numerical Analysis|páginas=249–285|editor-sobrenome=Zaremba|editor-nome=S. K.|url=https://www.sciencedirect.com/science/article/pii/B9780127759500500133|acessodata=2024-01-29|publicado=Academic Press|isbn=978-0-12-775950-0}}</ref>
{| class="wikitable"
!''d''
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|-
! ''&#x3BD;'' {{Su|p=2|b=''d''}}
| 4243209856
| 2072544
| 52804
| 6990
| 242
|-
! ''&#x3BC;''<sub>''d''</sub>{{nre|Calculado a partir de ''&nu;''{{su|p=2|b=''d''}} reportado por Marsaglia.}}
| 3.10
| 2,91
| 3.20
| 5.01
| 0,017
|-
! ''f''<sub>''d''</sub>{{nre|name=SSSoft}}
| 0,462490
| 0,313127
| 0,457183
| 0,552916
| 0,376706
| 0,496687
| 0,685247
|}
Os números agregados de mérito são: <math>\mathcal{M}^{*}_8(69069, 2^{32}) =0.313127</math>, <math>\mathcal{H}^{*}_8(69069, 2^{32}) = 0.449578</math>.{{nre|name=SSSoft}}

Steele & Vigna (2020) fornecem os multiplicadores com os maiores números agregados de mérito para muitas escolhas de ''m'' = 2<sup>''n''</sup> e um determinado comprimento de bit de ''a'' . Eles também fornecem os valores <math>f_d</math> e um pacote de software para calcular esses valores.<ref name="Steele20"/> {{rp|14&ndash;5}} Por exemplo, eles relatam que o melhor ''a'' de 17 bits para ''m'' = 2<sup>32</sup> é:

* Para um LCG (c &#x2260; 0),  (121525). <math>\mathcal{M}^{+}_8=0.6403</math>, <math>\mathcal{H}^{+}_8 = 0.6588</math>.<ref name="Steele20"/> {{rp|14}}
* Para um MCG (c = 0),  (125229). <math>\mathcal{M}^{*}_8=0.6623</math>, <math>\mathcal{H}^{*}_8 = 0.7497</math>.<ref name="Steele20" /> {{rp|14}}

== Ilustração adicional ==
{{Imagem múltipla
| width = 300
| align = center
| direction = horizontal
| image1 = Spectral test of 3x mod 31.png
| image12 = Spectral test of 13x mod 31.png
| footer = Apesar do fato de ambas as relações passarem no [[Qui-quadrado|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.
}}

== Notas ==
{{listanota}}

{{Referências}}

== Leitura adicional ==
* {{Citar periódico |título=Bad subsequences of well-known linear congruential pseudorandom number generators |data=janeiro de 1998 |periódico=ACM Transactions on Modeling and Computer Simulation |número=1 |ultimo=Entacher |primeiro=Karl |paginas=61–70 |doi=10.1145/272991.273009 |volume=8}} &#x2013; lista <math>f_d</math> (anotado como <math>S_s</math> neste texto) de muitos LCGs conhecidos
** Uma versão expandida desse trabalho está disponível como: {{Citar web|ultimo=Entacher|primeiro=Karl|url=https://www.researchgate.net/publication/2683298|titulo=A Collection of Selected Pseudorandom Number Generators With Linear Structures - extended version|data=2001}}<cite class="citation web cs1" id="CITEREFEntacher2001">[https://www.researchgate.net/publication/2683298 "A Collection of Selected Pseudorandom Number Generators With Linear Structures - extended version"].</cite>

[[Categoria:Testes estatísticos]]