Teste Espectral (estatística)
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).[1] 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.[2] O teste espectral compara a distância entre esses planos; quanto mais distantes eles estiverem, pior será o gerador.[3] 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,[4] this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM subroutine RANDU[5][6]
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
[editar | editar código-fonte]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[7]:3 onde são definidos como antes, e é a constante de Hermite de dimensão d . é a menor separação interplanar possível.[7] :3
L'Ecuyer (1991) introduziu ainda duas métricas correspondendo ao mínimo de em várias dimensões.[8] 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.[7] :13Eles definem ainda uma média ponderada de mérito “harmônica”, (e ).[7] :13
Exemplos
[editar | editar código-fonte]Uma pequena variante do algoritmo RANDU, com tem:[4] (Tabela 1)
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[a] | 0,520224 | 0,018902 | 0,084143 | 0,207185 | 0,368841 | 0,552205 | 0,578329 |
Os números agregados de mérito são: , .[a]
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.[9]
d | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|
ν 2 d |
4243209856 | 2072544 | 52804 | 6990 | 242 | ||
μd[b] | 3.10 | 2,91 | 3.20 | 5.01 | 0,017 | ||
fd[a] | 0,462490 | 0,313127 | 0,457183 | 0,552916 | 0,376706 | 0,496687 | 0,685247 |
Os números agregados de mérito são: , .[a]
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.[7] :14–5 Por exemplo, eles relatam que o melhor a de 17 bits para m = 232 é:
Ilustração adicional
[editar | editar código-fonte]Notas
[editar | editar código-fonte]Referências
- ↑ Williams, K. B.; Dwyer, Jerry (1 de agosto de 1996), «Testing Random Number Generators, Part 2», Dr. Dobb's Journal, consultado em 26 de janeiro de 2012.
- ↑ Marsaglia, George (setembro de 1968). «Random Numbers Fall Mainly in the Planes» (PDF). PNAS. 61 (1): 25–28. Bibcode:1968PNAS...61...25M. PMC 285899. PMID 16591687. doi:10.1073/pnas.61.1.25
- ↑ Jain, Raj. «Testing Random-Number Generators (Lecture)» (PDF). Washington University in St. Louis. Consultado em 2 de dezembro de 2016
- ↑ a b Knuth, Donald E. (1981), «3.3.4: The Spectral Test», The Art of Computer Programming volume 2: Seminumerical algorithms 2nd ed. , Addison-Wesley.
- ↑ IBM, System/360 Scientific Subroutine Package, Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.
- ↑ International Business Machines Corporation (1968). «IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III» (PDF). White Plains, NY: IBM Technical Publications Department. Stan's Library. II: 77. doi:10.3247/SL2Soft08.001. Scientific Application Program H20-0205-3
- ↑ a b c d e f g Steele, Guy L. Jr.; Vigna, Sebastiano (fevereiro de 2022). «Computationally easy, spectrally good multipliers for congruential pseudorandom number generators» (PDF). Software: Practice and Experience. 52 (2): 443–458. arXiv:2001.05304. doi:10.1002/spe.3030 Associated software and data at https://github.com/vigna/CPRNG.
- ↑ L'Ecuyer, Pierre (janeiro de 1999). «Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure» (PDF). Mathematics of Computation. 68 (225): 249–260. Bibcode:1999MaCom..68..249L. CiteSeerX 10.1.1.34.1024. doi:10.1090/S0025-5718-99-00996-5 Be sure to read the Errata as well.
- ↑ Marsaglia, GEORGE (1 de janeiro de 1972), Zaremba, S. K., ed., «The Structure of Linear Congruential Sequences», ISBN 978-0-12-775950-0, Academic Press, Applications of Number Theory to Numerical Analysis: 249–285, consultado em 29 de janeiro de 2024
Leitura adicional
[editar | editar código-fonte]- Entacher, Karl (janeiro de 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 (anotado como 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".