Wikipédia

Gerador de números pseudoaleatórios

 Nota: Para o aparato físico, veja Gerador de número pseudoaleatório (hardware).

Um gerador de número pseudo-aleatório (do inglês, PRNG, Pseudo-random Number Generator) é um algoritmo normalmente derivado de uma função matemática que gera uma seqüência de números, os quais são aproximadamente independentes um dos outros. A saída da maioria dos geradores de números aleatórios não é verdadeiramente aleatória; ela somente aproxima algumas das propriedades dos números aleatórios. John von Neumann enfatiza com este comentário "Qualquer um que considere métodos aritméticos para produzir dígitos está, certamente, cometendo um pecado". Enquanto números verdadeiramente aleatórios podem ser gerados usando hardware para geração de número aleatório. Alguns exemplos de números aleatórios são: tempo de resposta de requisições de leitura de um disco rígido e tubos de descarga de gás. Número pseudo-aleatórios são uma parte crítica da computação moderna, da criptografia até o método de Monte Carlo passando por sistemas de simulação. Uma cuidadosa análise matemática é necessária para assegurar que a geração dos números seja suficientemente "aleatória".[carece de fontes?]

Lista de Geradores de Números Pseudoaleatórios editar

Abaixo, encontra-se uma lista de geradores que marcaram historicamente o campo de estudo do processo de geração de números pseudoaleatórios, seja por sua importância histórica ou por ser um modelo inovador considerando as suas respectivas épocas. Ademais, apesar de serem PRNGs alguns destes podem ser aplicáveis dentro do campo da criptografia.

Modelo Ano Autores Referências Descrição
Quadrado Médio 1946 John von Neumann [1] Um PRNG considerado de baixa qualidade mas de grande relevância histórica por ser um dos pioneiros algoritmos.
Gerador de Lehmer 1951 D.H. Lehmer [2] Também conhecido como método Congruencial Linear Multiplicativo e de grande influência neste campo de estudo.
Gerador Congruencial Linear 1958 W.E. Thomson [3] Modelo derivado de Lehmer (1951) de grande influência e demasiado estudado em todo o mundo.
Gerador Lagged Fibonacci (LFG) 1958 G. J. Mitchell; D. P. Moore [4] Um algoritmo altamente influente no campo de estudo de processos de geração de números aleatórios que inspirou outros grandes autores subsequentes como George Marsaglia, o criador do Teste de qualidade de números aleatórios denominado "Diehard", por exemplo.
Linear-feedback Shift Register (LFSR) 1965 R. C. Tausworthe [5] Um gerador cujo design influenciou muitos outros PRNGs seguintes. Portanto, muito importante historicamente. Também conhecido como Gerador de Tausworthe.
Gerador de Wichmann & Hill 1982 B. A. Wichmann; D. I. Hill [6] Uma combinação de três pequenos LCGs, adequados para CPUs de 16 bits. Amplamente usado em muitos programas, por exemplo, foi usado no Excel 2003 e em mais algumas versões posteriores para a função RAND do Excel e foi o gerador padrão na linguagem Python até a versão 2.2.
Rule 30 1983 S. Wolfram [7] Gerador baseado em autômatos celulares.
Blum-Blum-Shub 1986 M. Blum; L. Blum; M. Shub [8] Considerado um dos geradores mais seguros do ponto de vista criptográfico, sobretudo, devido a implementação em sua fórmula, estudos e conceitos oriundos da teoria dos números.
Gerador de Park-Miller 1988 S. K. Park; K. W. Miller [9] Uma implementação específica de um gerador Lehmer, amplamente utilizado porque está incluído em C++ como a função minstd_rand0 de C++11 em diante.
MIXMAX 1991 G. K. Savvidy; N. G. Ter-Arutyunyan-Savvidy [10] É um gerador pertencente a classe de gerador linear de congruência matricial, uma generalização do Método Congruencial Linear. A lógica por trás da família de geradores MIXMAX baseia-se nos resultados da teoria ergódica e da mecânica clássica.
Add-with-carry (AWC) 1991 G. Marsaglia; A. Zaman [11] Uma modificação dos geradores Lagged-Fibonacci.
Subtract-with-borrow (SWB) 1991 G. Marsaglia; A. Zaman [11] Algoritmo derivado dos geradores Lagged-Fibonacci.
ISAAC 1993 R.J. Jenkins [12] Gerador criptograficamente seguro (CSPRNG) desenvolvido por Robert J. Jenkins.
Mersenne Twister (MT) 1998 M. Matsumoto; N. Makoto [13] Provavelmente o PRNG mais conhecido contido nessa lista, principalmente, por ser um algoritmo implementado nas funções RAND nas linguagens de programação Python e R, além de sua grande presença em jogos eletrônicos como em Pro Evolution Soccer (PES).
Xorshift 2003 G. Marsaglia [14] É um subtipo muito rápido de geradores LFSR. Marsaglia também sugeriu como uma melhoria o gerador xorwow, no qual a saída de um gerador xorshift é adicionada com uma seqüência Weyl. O gerador xorwow é o gerador padrão na biblioteca CURAND da interface de programação da aplicação nVidia CUDA para unidades de processamento gráfico.
Fortuna 2003 B. Schneier; N. Ferguson [carece de fontes?] Algoritmo considerado criptográficamente seguro. Conhecido por ser um CSPRNG implementado nos sistemas e produtos da Apple.
Well equidistributed long-period linear (WELL) 2006 F. Panneton, P. L'Ecuyer; M. Matsumoto [15] Algoritmo conhecido por ser complementar ao Mersenne Twister (MT), buscando de forma deliberada cobrir seus pontos limitantes.
Advanced Randomization System (ARS) 2011 J. Salmon, M. Moraes, R. Dror; D. Shaw [16] Uma versão simplificada da cifra do bloco AES, levando a um desempenho muito rápido no sistema que suporta o AES-NI.
Permuted Congruential Generator (PCG) 2014 M. E. O'Neill [17] Um modelo derivado do Método Congruencial Linear.
Random Cycle Bit Generator (RCB) 2016 R. Cookman [18] O RCB é descrito como um gerador de padrão de bits feito para superar algumas das deficiências com o Mersenne Twister (MT) e a restrição de curto período/ duração de bits dos geradores de turno/módulo.
Xoroshiro128+ 2018 D. Blackman; S. Vigna [19] Uma modificação dos geradores Xorshift de G. Marsaglia, um dos geradores mais rápidos nas CPUs modernas de 64 bits. Os geradores relacionados incluem xoroshiro128**, xoshiro256+ e xoshiro256***.
64-bit MELG (MELG-64) 2018 S. Harase; T. Kimoto [20] Uma implementação de geradores F2 lineares de 64 bits com o período primário Mersenne.
Squares RNG 2020 B. Widynski [21] Gerador derivado do método do Quadrado Médio proposto por John von Neumann
Itamaracá (Ita) 2021 D.H. Pereira [22] Conhecido por ser o primeiro algoritmo PRNG que possui a Função de Valor Absoluto em sua base. Itamaracá apresenta-se também como um modelo simples, rápido e que gera sequências de números aleatórios aperiódicos.

Ver também editar

Referências

  1. ↑ «Annual report 1951 National Bureau of Standards». Gaithersburg, MD. 1951. Consultado em 10 de maio de 2022 
  2. ↑ Curtiss, J. H. (abril de 1947). «A Symposium of Large Scale Digital Calculating Machinery». Mathematical Tables and Other Aids to Computation (18). 229 páginas. ISSN 0891-6837. doi:10.2307/2002294. Consultado em 10 de maio de 2022 
  3. ↑ Thomson, W. E. (1 de fevereiro de 1958). «A Modified Congruence Method of Generating Pseudo-random Numbers». The Computer Journal (em inglês) (2): 83–83. ISSN 0010-4620. doi:10.1093/comjnl/1.2.83. Consultado em 10 de maio de 2022 
  4. ↑ Wrench, J. W. (1970). «Table errata: The art of computer programming, Vol. 2: Seminumerical algorithms (Addison-Wesley, Reading, Mass., 1969) by Donald E. Knuth». Mathematics of Computation (110). 504 páginas. ISSN 0025-5718. doi:10.1090/s0025-5718-1970-0400642-2. Consultado em 11 de maio de 2022 
  5. ↑ Tausworthe, Robert C. (1965). «Random numbers generated by linear recurrence modulo two». Mathematics of Computation (em inglês) (90): 201–209. ISSN 0025-5718. doi:10.1090/S0025-5718-1965-0184406-1. Consultado em 10 de maio de 2022 
  6. ↑ Wichmann, B. A.; Hill, I. D. (1982). «Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator». Journal of the Royal Statistical Society. Series C (Applied Statistics) (2): 188–190. ISSN 0035-9254. doi:10.2307/2347988. Consultado em 10 de maio de 2022 
  7. ↑ Wolfram, Stephen (1 de julho de 1983). «Statistical mechanics of cellular automata». Reviews of Modern Physics (3): 601–644. doi:10.1103/RevModPhys.55.601. Consultado em 10 de maio de 2022 
  8. ↑ Blum, L.; Blum, M.; Shub, M. (1 de maio de 1986). «A Simple Unpredictable Pseudo-Random Number Generator». SIAM Journal on Computing (2): 364–383. ISSN 0097-5397. doi:10.1137/0215025. Consultado em 10 de maio de 2022 
  9. ↑ Park, S. K.; Miller, K. W. (1 de outubro de 1988). «Random number generators: good ones are hard to find». Communications of the ACM (10): 1192–1201. ISSN 0001-0782. doi:10.1145/63039.63042. Consultado em 10 de maio de 2022 
  10. ↑ Savvidy, G. K; Ter-Arutyunyan-Savvidy, N. G (1 de dezembro de 1991). «On the Monte Carlo simulation of physical systems». Journal of Computational Physics (em inglês) (2): 566–572. ISSN 0021-9991. doi:10.1016/0021-9991(91)90015-D. Consultado em 10 de maio de 2022 
  11. ↑ a b Marsaglia, George; Zaman, Arif (agosto de 1991). «A New Class of Random Number Generators». The Annals of Applied Probability (3): 462–480. ISSN 1050-5164. doi:10.1214/aoap/1177005878. Consultado em 10 de maio de 2022 
  12. ↑ «ISAAC, a fast cryptographic random number generator». www.burtleburtle.net. Consultado em 10 de maio de 2022 
  13. ↑ Matsumoto, Makoto; Nishimura, Takuji (1 de janeiro de 1998). «Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator». ACM Transactions on Modeling and Computer Simulation (1): 3–30. ISSN 1049-3301. doi:10.1145/272991.272995. Consultado em 10 de maio de 2022 
  14. ↑ Marsaglia, George (4 de julho de 2003). «Xorshift RNGs». Journal of Statistical Software (em inglês): 1–6. ISSN 1548-7660. doi:10.18637/jss.v008.i14. Consultado em 10 de maio de 2022 
  15. ↑ Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (1 de março de 2006). «Improved long-period generators based on linear recurrences modulo 2». ACM Transactions on Mathematical Software (1): 1–16. ISSN 0098-3500. doi:10.1145/1132973.1132974. Consultado em 10 de maio de 2022 
  16. ↑ Salmon, John K.; Moraes, Mark A.; Dror, Ron O.; Shaw, David E. (12 de novembro de 2011). «Parallel random numbers: as easy as 1, 2, 3». New York, NY, USA: Association for Computing Machinery. SC '11: 1–12. ISBN 978-1-4503-0771-0. doi:10.1145/2063384.2063405. Consultado em 10 de maio de 2022 
  17. ↑ Sileshi, B.G.; Ferrer, C.; Oliver, J. (novembro de 2014). «Accelerating hardware Gaussian random number generation using Ziggurat and CORDIC algorithms». IEEE. doi:10.1109/icsens.2014.6985457. Consultado em 10 de maio de 2022 
  18. ↑ «Random Bit Generator». Berlin/Heidelberg: Springer-Verlag. SpringerReference. Consultado em 10 de maio de 2022 
  19. ↑ Blackman, David; Vigna, Sebastiano (28 de março de 2022). «Scrambled Linear Pseudorandom Number Generators». arXiv:1805.01407 [cs]. Consultado em 10 de maio de 2022 
  20. ↑ Harase, Shin; Kimoto, Takamitsu (3 de janeiro de 2018). «Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period». ACM Transactions on Mathematical Software (3): 30:1–30:11. ISSN 0098-3500. doi:10.1145/3159444. Consultado em 10 de maio de 2022 
  21. ↑ Widynski, Bernard (13 de março de 2022). «Squares: A Fast Counter-Based RNG». arXiv:2004.06278 [cs]. Consultado em 10 de maio de 2022 
  22. ↑ Pereira, Daniel Henrique (25 de janeiro de 2022). «Itamaracá: A Novel Simple Way to Generate Pseudo-random Numbers» (em inglês). doi:10.33774/coe-2022-zsw6t. Consultado em 10 de maio de 2022 

Ligações externas editar

  Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.
Obtida de "https://pt.wikipedia.org/w/index.php?title=Gerador_de_números_pseudoaleatórios&oldid=67482764"