Mersenne Twister
O Mersenne Twister é um gerador de números pseudoaleatórios de uso geral (PRNG) desenvolvido em 1997 por Makoto Matsumoto (松本 眞, Makoto Matsumoto?) e Takuji Nishimura (西村 拓士, Takuji Nishimura?) . [1] [2] Seu nome deriva da escolha de um primo de Mersenne como duração do seu período.
A versão mais comumente usada desteo algoritmo é baseada no primo de Mersenne . A implementação padrão, MT19937, usa um comprimento de palavra de 32 bits. Existe outra implementação (que apresenta ainda cinco variantes[3]) que usa um comprimento de palavra de 64 bits, MT19937-64; ela gera uma sequência diferente.
k-distribuição
Uma sequência pseudoaleatória de inteiros de w bits do período P é dita ser k-distribuída com precisão de v bits se a seguinte afirmação for verdadeira.
- Seja trunc v ( x ) o número formado pelos bits v iniciais de x, e considere P dos k vetores de v bits
- .
- Então cada um dos combinações possíveis de bits ocorrem o mesmo número de vezes em um período, exceto pela combinação de zeros que ocorre uma vez com menos frequência.
Detalhe do algoritmo
Para palavras de comprimento w bits, o Mersenne Twister gera inteiros no intervalo .
O algoritmo é baseado em uma recorrência linear de matriz sobre um campo binário finito . O algoritmo é um registrador de deslocamento de feedback generalizado torcido[4] (GFSR torcido ou TGFSR) de forma normal racional (TGFSR(R)), com reflexão de bits de estado e moderação. A ideia básica é definir uma série por meio de uma relação de recorrência simples e, em seguida, gerar números da forma , onde T é uma matriz inversível chamada matriz de têmpera.
O algoritmo geral é caracterizado pelas seguintes quantidades:
- w : tamanho da palavra (em número de bits)
- n : grau de recorrência
- m : palavra do meio, um deslocamento usado na relação de recorrência que define a série ,
- r : ponto de separação de uma palavra, ou o número de bits da máscara de bits inferior,
- a : coeficientes da matriz de torção da forma normal racional
- b, c : máscaras de bits de têmpera TGFSR(R)
- s, t : Mudanças de bits de têmpera TGFSR(R)
- u, d, l : mudanças/máscaras adicionais de bits de têmpera Mersenne Twister
sendo que é um primo de Mersenne. Essa escolha simplifica o teste de primitividade e o teste de distribuição k que são necessários para a aquisição de parâmetros.
A série é definida como uma série de quantidades de w bits com a relação:
onde denota concatenação de vetores de bits (com bits superiores à esquerda), o bitwise ou-exclusivo (XOR), significa os bits w − r superiores de , e significa os bits r inferiores de .
Os subscritos podem ser todos compensados por -n
onde o LHS, , é o próximo valor gerado na série em termos de valores gerados no passado, que estão no RHS.
A transformação de torção A é definida na forma normal racional como: com como o matriz identidade. A forma normal racional tem o benefício de que a multiplicação por A pode ser expressa eficientemente como: onde é o bit de ordem mais inferior do vetor .
Assim como o TGFSR(R), o Mersenne Twister é cascateado com uma transformação de moderação para compensar a dimensionalidade reduzida da equidistribuição (devido à escolha de A estar na forma normal racional). Observe que isso é equivalente a usar a matriz A onde para T uma matriz inversível e, com isso, a análise do polinômio característico mencionada abaixo ainda é válida.
Assim como em A, escolhemos uma transformação de têmpera para ser facilmente computável e, portanto, não construímos T propriamente dito. Esta têmpera é definida no caso do Mersenne Twister como sendo
onde é o próximo valor da série, é um valor intermediário temporário e é o valor retornado do algoritmo, com e como os deslocamentos bit a bit para a esquerda e para a direita, e como o bit a bit AND. A primeira e a última transformações são adicionadas para melhorar a equidistribuição de bits mais baixos. Da propriedade do TGFSR, é necessário para atingir o limite superior da equidistribuição para os bits superiores.
Os coeficientes para MT19937 são:
Observe que as implementações de 32 bits do Mersenne Twister geralmente têm d = FFFFFFFF16. Como resultado, o d é geralmente omitido da descrição do algoritmo, já que o AND com d nesse caso não têm efeito.
Os coeficientes para MT19937-64 são:[5]
Inicialização
O estado necessário para uma implementação do Mersenne Twister é uma matriz de n valores de w bits cada. Para inicialização da matriz, um valor de semente de w bits é usado para fornecer através através da configuração de para o valor da semente e, posteriormente, a configuração
para de para .
- O primeiro valor que o algoritmo gera é baseado em , não em .
- A constante f forma outro parâmetro para o gerador, embora não faça parte do algoritmo propriamente dito.
- O valor de f para MT19937 é 1812433253.
- O valor de f para MT19937-64 é 6364136223846793005. [5]
Comparação com GFSR clássico
Para atingir o limite superior teórico do período em um TGFSR, deve ser um polinômio primitivo, sendo o polinômio característico de
A transformação de torção traz melhorias para o GFSR clássico com as seguintes propriedades principais:
- O período atinge o limite superior teórico (exceto se inicializado com 0)
- Equidistribuição em n dimensões (por exemplo, geradores congruentes lineares podem, na melhor das hipóteses, gerenciar uma distribuição razoável em cinco dimensões)
Variantes
CryptMT é uma cifra de fluxo e um gerador de números pseudoaleatórios criptograficamente seguro que usa Mersenne Twister como base interna.[6] [7] Também foi desenvolvida por Matsumoto e Nishimura, em conjunto com Mariko Hagita e Mutsuo Saito. Foi submetida ao projeto eSTREAM da rede eCRYPT.[6] Ao contrário do Mersenne Twister ou seus outros derivados, o CryptMT é patenteado.
MTGP é uma variante do Mersenne Twister otimizada para unidades de processamento gráfico publicadas por Mutsuo Saito e Makoto Matsumoto.[8] As operações de recorrência linear são estendidas da MT e os parâmetros são escolhidos para permitir que muitos threads calculem a recursão em paralelo, enquanto compartilham seu espaço de estado para reduzir a quantidade de memória usada. O artigo afirma que houve uma melhora na equidistribuição em MT e no desempenho, com base em uma GPU antiga (era 2008) (Nvidia GTX260 com 192 núcleos) de 4,7 ms para 5×107 inteiros aleatórios de 32 bits.
O SFMT (Mersenne Twister rápido orientado a SIMD) é uma variante do Mersenne Twister, introduzida em 2006,[9] projetado para ser rápida quando executada em SIMDs de 128 bits.
- É quase duas vezes mais rápido que o Mersenne Twister.[10]
- Ele tem uma propriedade de equidistribuição de precisão de v-bit melhor que o MT, mas pior que oWELL ("Well Equidistributed Long-period Linear") .
- Ele tem uma recuperação mais rápida do estado inicial de excesso zero do que o MT, mas mais lenta do que o WELL.
- Ele suporta vários períodos de 2 607 − 1 a 2 216091 − 1.
Intel SSE2 e PowerPC AltiVec utilizam a variante SFMT, que também é usada para jogos com o Cell BE no PlayStation 3.[11]
TinyMT é uma variante do Mersenne Twister, proposto por Saito e Matsumoto em 2011.[12] O TinyMT usa apenas 127 bits de espaço de estado, uma diminuição significativa em comparação aos 2,5 KiB de estado do original. No entanto, tem um período de , que é muito mais curto que a proposta original, por isso
é uma variante somente recomendada em casos em que a memória é escassa.
Características
Vantagens:
- Com licença permissiva e livre de patentes para todas as variantes, exceto CryptMT.
- Passa em vários testes de aleatoriedade estatística, incluindo os testes Diehard e a maioria, mas não todos os testes TestU01.[13]
- Um período muito longo de . Observe que um longo período não é garantia de qualidade em um gerador de números aleatórios, períodos curtos, como o comum em muitos pacotes de software mais antigos, pode ser problemático.[14]
- As implementações geralmente criam números aleatórios mais rapidamente do que os métodos implementados por hardware. Um estudo descobriu que o Mersenne Twister cria números aleatórios de ponto flutuante de 64 bits aproximadamente vinte vezes mais rápido do que o conjunto de instruções RDRAND baseado em processador e implementado por hardware.[15]
Desvantagens:
- Buffer de estado relativamente grande, de quase 2,5 kB, a menos que a variante TinyMT seja usada.
- Rendimento medíocre para os padrões modernos, a menos que a variante SFMT (discutida abaixo) seja usada.[16]
- Exibe duas falhas claras (complexidade linear) tanto no Crush quanto no BigCrush no conjunto TestU01. O teste, como o Mersenne Twister, é baseado em um -álgebra.[13]
- Várias instâncias que diferem apenas no valor da semente (mas não em outros parâmetros) geralmente não são apropriadas para simulações de Monte Carlo que requerem geradores de números aleatórios independentes, embora exista um método para escolher vários conjuntos de valores de parâmetros.[17][18]
- Difusão ruim: pode levar muito tempo para começar a gerar uma saída que passe nos testes de aleatoriedade, se o estado inicial for altamente não aleatório, principalmente se o estado inicial tiver muitos zeros. Uma consequência disso é que duas instâncias do gerador, iniciadas com estados iniciais quase iguais, geralmente produzirão quase a mesma sequência por muitas iterações, antes de eventualmente divergir. A atualização de 2002 do algoritmo MT melhorou a inicialização, de modo que começar com tal estado é muito improvável. [19] Diz-se que a versão GPU (MTGP) é ainda melhor.[20]
- Contém subsequências com mais 0's do que 1's. Isso contribui para a baixa propriedade de difusão, dificultando a recuperação de estados com muitos zeros.
- Não é criptograficamente seguro, a menos que a variante CryptMT (discutida abaixo) seja usada. O motivo é que observar um número suficiente de iterações (624 no caso do MT19937, já que esse é o tamanho do vetor de estado a partir do qual as iterações futuras são produzidas) permite prever todas as iterações futuras.
Aplicações
O Mersenne Twister é usado como gerador padrão pelos softwares:
- Linguagens de programação: Dyalog APL,[21] IDL,[22] R,[23] Ruby,[24] Free Pascal,[25] PHP,[26] Python (também disponível em NumPy, no entanto o padrão foi alterado para PCG64 a partir da versão 1.17[27] ), [28][29][30] CMU Common Lisp,[31] Embeddable Common Lisp, [32] Steel Bank Common Lisp,[33] Julia (até Julia 1.6 LTS, ainda disponível em versões posteriores, mas um RNG melhor/mais rápido usado por padrão a partir da versão 1.7)[34]
- Bibliotecas e software do tipo Unix : GLib,[35] GNU Multiple Precision Arithmetic Library,[36] GNU Octave,[37] GNU Scientific Library[38]
- Outros: Microsoft Excel,[39] GAUSS,[40] gretl,[41] Stata,[42] SageMath,[43] Scilab,[44] Maple,[45] MATLAB[46]
Também está disponível no Apache Commons,[47] na biblioteca C++ padrão (desde C++11 ),[48][5] e no Mathematica.[49] Implementações de complementos são fornecidas em muitas bibliotecas de programas, incluindo as Bibliotecas Boost C++,[50] a Biblioteca CUDA,[51] e a Biblioteca Numérica NAG.[52]
O Mersenne Twister é um dos dois PRNGs no SPSS: o outro gerador é mantido apenas para compatibilidade com programas mais antigos, e o Mersenne Twister é considerado "mais confiável".[53] Também é de igual maneira um dos PRNGs no SAS: os outros geradores estão presentes apenas pelo fator de compatibilidade.[54] O Mersenne Twister é o PRNG padrão no Stata, o outro é o KISS, para compatibilidade com versões mais antigas do Stata.[55]
Alternativas
O gerador WELL ("Well Equidistributed Long-period Linear"), oferece recuperação mais rápida, aleatoriedade igual e velocidade quase igual.[56]
Geradores xorshift e variantes da Marsaglia são os mais rápidos na classe de LFSRs.[57]
MELGs de 64 bits ("Geradores -Lineares de 64 bits maximamente equidistribuídos com Período Primo de Mersenne") são completamente otimizados em termos das propriedades de distribuição k .[58]
A família ACORN (publicada inicialmente em 1989) é outro gerador k -distribuído, que apresenta velocidade computacional similar à MT e melhores propriedades estatísticas, pois satisfaz todos os critérios do TestU01; quando usado com escolhas apropriadas de parâmetros, o ACORN pode ter período e precisão arbitrariamente longos.
A família PCG é um gerador de longo período mais moderno, com melhor uso de cache e menos viés detectável usando métodos de análise modernos.[59]
Referências
- ↑ Matsumoto, M.; Nishimura, T. (1998). «Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator». ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995
- ↑ E.g. Marsland S. (2011) Machine Learning (CRC Press), §4.1.1. Also see the section "Adoption in software systems".
- ↑ John Savard. «The Mersenne Twister»
- ↑ Matsumoto, M.; Kurita, Y. (1992). «Twisted GFSR generators». ACM Transactions on Modeling and Computer Simulation. 2 (3): 179–194. doi:10.1145/146382.146383
- ↑ a b c «std::mersenne_twister_engine». Pseudo Random Number Generation. Consultado em 20 de julho de 2015
- ↑ a b «CryptMt and Fubuki». eCRYPT. Consultado em 12 de novembro de 2017. Arquivado do original em 1 de julho de 2012
- ↑ Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo (2005). «Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher» (PDF)
- ↑ Mutsuo Saito; Makoto Matsumoto. «Variants of Mersenne Twister Suitable for Graphic Processors». arXiv:1005.4973v3 [cs.MS]
- ↑ «SIMD-oriented Fast Mersenne Twister (SFMT)». hiroshima-u.ac.jp. Consultado em 4 outubro 2015
- ↑ «SFMT:Comparison of speed». hiroshima-u.ac.jp. Consultado em 4 outubro 2015
- ↑ «PlayStation3 License». scei.co.jp. Consultado em 4 outubro 2015
- ↑ «Tiny Mersenne Twister (TinyMT)». hiroshima-u.ac.jp. Consultado em 4 outubro 2015
- ↑ a b P. L'Ecuyer and R. Simard, "TestU01: "A C library for empirical testing of random number generators", ACM Transactions on Mathematical Software, 33, 4, Article 22 (agosto 2007).
- ↑ Note: 219937 is approximately 4.3 × 106001; this is many orders of magnitude larger than the estimated number of particles in the observable universe, which is 1087.
- ↑ Route, Matthew (agosto 10, 2017). «Radio-flaring Ultracool Dwarf Population Synthesis». The Astrophysical Journal. 845 (1): 66. Bibcode:2017ApJ...845...66R. arXiv:1707.02212. doi:10.3847/1538-4357/aa7ede
- ↑ «SIMD-oriented Fast Mersenne Twister (SFMT): twice faster than Mersenne Twister». Japan Society for the Promotion of Science. Consultado em 27 março 2017
- ↑ Makoto Matsumoto; Takuji Nishimura. «Dynamic Creation of Pseudorandom Number Generators» (PDF). Consultado em 19 julho 2015
- ↑ Hiroshi Haramoto; Makoto Matsumoto; Takuji Nishimura; François Panneton; Pierre L'Ecuyer. «Efficient Jump Ahead for F2-Linear Random Number Generators» (PDF). Consultado em 12 Nov 2015
- ↑ «mt19937ar: Mersenne Twister with improved initialization». hiroshima-u.ac.jp. Consultado em 4 outubro 2015
- ↑ Fog, Agner (1 maio 2015). «Pseudo-Random Number Generators for Vector Processors and Multicore Processors». Journal of Modern Applied Statistical Methods. 14 (1): 308–334. doi:10.22237/jmasm/1430454120
- ↑ «Random link». Dyalog Language Reference Guide. Consultado em 4 de junho de 2020
- ↑ «RANDOMU (IDL Reference)». Exelis VIS Docs Center. Consultado em 23 de agosto de 2013
- ↑ «Random Number Generators». CRAN Task View: Probability Distributions. Consultado em 29 de maio de 2012
- ↑ «"Random" class documentation». Ruby 1.9.3 documentation. Consultado em 29 de maio de 2012
- ↑ «random». free pascal documentation. Consultado em 28 de novembro de 2013
- ↑ «mt_rand — Generate a better random value». PHP Manual. Consultado em 2 de março de 2016
- ↑ «NumPy 1.17.0 Release Notes — NumPy v1.21 Manual». numpy.org. Consultado em 29 de junho de 2021
- ↑ «9.6 random — Generate pseudo-random numbers». Python v2.6.8 documentation. Consultado em 29 de maio de 2012
- ↑ «8.6 random — Generate pseudo-random numbers». Python v3.2 documentation. Consultado em 29 de maio de 2012
- ↑ «random — Generate pseudo-random numbers — Python 3.8.3 documentation». Python 3.8.3 documentation. Consultado em 23 de junho de 2020
- ↑ «Design choices and extensions». CMUCL User's Manual. Consultado em 3 de fevereiro de 2014
- ↑ «Random states». The ECL manual. Consultado em 20 de setembro de 2015
- ↑ «Random Number Generation». SBCL User's Manual
- ↑ «Random Numbers · The Julia Language». docs.julialang.org. Consultado em 21 de junho de 2022
- ↑ «Random Numbers: GLib Reference Manual»
- ↑ «Random Number Algorithms». GNU MP. Consultado em 21 de novembro de 2013
- ↑ «16.3 Special Utility Matrices». GNU Octave
- ↑ «Random number environment variables». GNU Scientific Library. Consultado em 24 de novembro de 2013
- ↑ Mélard, G. (2014), «On the accuracy of statistical procedures in Microsoft Excel 2010», Computational Statistics, 29 (5): 1095–1128, doi:10.1007/s00180-014-0482-5 .
- ↑ «GAUSS 14 Language Reference» (PDF)
- ↑ "uniform". Gretl Function Reference.
- ↑ «New random-number generator—64-bit Mersenne Twister»
- ↑ «Probability Distributions — Sage Reference Manual v7.2: Probablity»
- ↑ «grand - Random numbers». Scilab Help
- ↑ «random number generator». Maple Online Help. Consultado em 21 de novembro de 2013
- ↑ «Random number generator algorithms». Documentation Center, MathWorks
- ↑ «Data Generation». Apache Commons Math User Guide
- ↑ «Random Number Generation in C++11» (PDF). Standard C++ Foundation
- ↑ [1] Mathematica Documentation
- ↑ «boost/random/mersenne_twister.hpp». Boost C++ Libraries. Consultado em 29 de maio de 2012
- ↑ «Host API Overview». CUDA Toolkit Documentation. Consultado em 2 de agosto de 2016
- ↑ «G05 – Random Number Generators». NAG Library Chapter Introduction. Consultado em 29 de maio de 2012
- ↑ «Random Number Generators». IBM SPSS Statistics. Consultado em 21 de novembro de 2013
- ↑ «Using Random-Number Functions». SAS Language Reference. Consultado em 21 de novembro de 2013
- ↑ Stata help: set rng -- Set which random-number generator (RNG) to use
- ↑ P. L'Ecuyer, "Uniform Random Number Generators", International Encyclopedia of Statistical Science, Lovric, Miodrag (Ed.), Springer-Verlag, 2010.
- ↑ «xorshift*/xorshift+ generators and the PRNG shootout»
- ↑ Harase, S.; Kimoto, T. (2018). «Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period». ACM Transactions on Mathematical Software. 44 (3): 30:1–30:11. arXiv:1505.06582. doi:10.1145/3159444
- ↑ «The PCG Paper». 27 julho 2017
Leitura adicional
- Harase, S. (2014), «On the -linear relations of Mersenne Twister pseudorandom number generators», Mathematics and Computers in Simulation, 100: 103–113, arXiv:1301.5435, doi:10.1016/j.matcom.2014.02.002 .
- Harase, S. (2019), «Conversion of Mersenne Twister to double-precision floating-point numbers», Mathematics and Computers in Simulation, 161: 76–83, arXiv:1708.06018, doi:10.1016/j.matcom.2018.08.006 .
Ligações externas
- O artigo acadêmico para MT e artigos relacionados de Makoto Matsumoto
- Página inicial do Mersenne Twister, com códigos em C, Fortran, Java, Lisp e algumas outras linguagens
- Exemplos de Mersenne Twister — uma coleção de implementações de Mersenne Twister, em várias linguagens de programação - no GitHub
- SFMT em Ação: Parte I – Gerando uma DLL Incluindo Suporte SSE2 – no Code Project