Mersenne Twister

O Mersenne Twister é um gerador de números pseudoaleatórios de uso geral (PRNG) desenvolvido em 1997 por Predefinição:Japonês e Predefinição:Japonês . 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 $2^{19937}-1$. A implementação padrão, MT19937, usa um comprimento de palavra de 32 bits. Existe outra implementação (que apresenta ainda cinco variantes) 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 $x_i$ 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

$({\mathrm{trunc}}_v(x_i),{\mathrm{trunc}}_v(x_{i+1}),\dots ,{\mathrm{trunc}}_v(x_{i+k-1}))(0\le i<P)$ .

Então cada um dos $2^{kv}$ 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

Visualização da geração de inteiros pseudoaleatórios de 32 bits usando Mersenne Twister. A seção Extract number mostra um exemplo em que o inteiro 0 já foi gerado e o índice está no inteiro 1. Generate numbers é executado quando todos os inteiros foram gerados.

Para palavras de comprimento w bits, o Mersenne Twister gera inteiros no intervalo $[0,2^w-1]$.

O algoritmo é baseado em uma recorrência linear de matriz sobre um campo binário finito ${\mathbf{\text{F}}}_2$ . O algoritmo é um registrador de deslocamento de feedback generalizado torcido (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 $x_i$ por meio de uma relação de recorrência simples e, em seguida, gerar números da forma $x_i^T$, onde T é uma matriz inversível ${\mathbf{\text{F}}}_2$ 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 $x$, $1\le m<n$
• r : ponto de separação de uma palavra, ou o número de bits da máscara de bits inferior, $0\le r\le w-1$
• 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 $2^{nw-r}-1$ é 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 $x$ é definida como uma série de quantidades de w bits com a relação:

$x_{k+n}:=x_{k+m}\oplus (({x_k}^u\mid {x_{k+1}}^l)A)k=0,1,2,\dots$

onde $\mid$ denota concatenação de vetores de bits (com bits superiores à esquerda), $\oplus$ o bitwise ou-exclusivo (XOR), $x_k^u$ significa os bits Predefinição:Nowrap superiores de $x_k$, e $x_{k+1}^l$ significa os bits r inferiores de $x_{k+1}$.

Os subscritos podem ser todos compensados por -n

$x_k:=x_{k-(n-m)}\oplus (({x_{k-n}}^u\mid {x_{k-(n-1)}}^l)A)k=n,n+1,n+2,\dots$

onde o LHS, $x_k$, é 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: $$A=\left(\begin{array}{cc}0& I_{w-1}\\ a_{w-1}& (a_{w-2},\dots ,a_0)\end{array}\right)$$ com $I_{w-1}$ como o $(w-1)(w-1)$ matriz identidade. A forma normal racional tem o benefício de que a multiplicação por A pode ser expressa eficientemente como: $$𝒙A=\{\begin{array}{cc}𝒙\gg 1& x_0=0\\ (𝒙\gg 1)\oplus 𝒂& x_0=1\end{array}$$ onde $x_0$ é o bit de ordem mais inferior do vetor $x$.

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 $A=T^{-1}*AT$ 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

$\begin{array}{cc}y& \equiv x\oplus ((x\gg u)\mathrm{\&}d)\\ y& \equiv y\oplus ((y\ll s)\mathrm{\&}b)\\ y& \equiv y\oplus ((y\ll t)\mathrm{\&}c)\\ z& \equiv y\oplus (y\gg l)\end{array}$

onde $x$ é o próximo valor da série, $y$ é um valor intermediário temporário e $z$ é o valor retornado do algoritmo, com $\ll$ e $\gg$ como os deslocamentos bit a bit para a esquerda e para a direita, e $\mathrm{\&}$ 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, $s+t\ge \lfloor \frac{w}{2}\rfloor -1$ é necessário para atingir o limite superior da equidistribuição para os bits superiores.

Os coeficientes para MT19937 são:

$\begin{array}{cc}(w,n,m,r)& =(32,624,397,31)\\ a& ={\text{9908B0DF}}_{16}\\ (u,d)& =(11,{\text{FFFFFFFF}}_{16})\\ (s,b)& =(7,{\text{9D2C5680}}_{16})\\ (t,c)& =(15,{\text{EFC60000}}_{16})\\ l& =18\\ \end{array}$

Observe que as implementações de 32 bits do Mersenne Twister geralmente têm d = FFFFFFFF₁₆. 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:

$\begin{array}{c}(w,n,m,r)=(64,312,156,31)\\ a={\text{B5026F5AA96619E9}}_{16}\\ (u,d)=(29,{\text{5555555555555555}}_{16})\\ (s,b)=(17,{\text{71D67FFFEDA60000}}_{16})\\ (t,c)=(37,{\text{FFF7EEE000000000}}_{16})\\ l=43\\ \end{array}$

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 $x_0$ através $x_{n-1}$ através da configuração de $x_0$ para o valor da semente e, posteriormente, a configuração

$x_i=f\times (x_{i-1}\oplus (x_{i-1}\gg (w-2)))+i$

para $i$ de $1$ para $n-1$ .

• O primeiro valor que o algoritmo gera é baseado em $x_n$, não em $x_0$ .
• 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.

Comparação com GFSR clássico

Para atingir o limite superior teórico do período $2^{nw-r}-1$ em um TGFSR, ${\varphi }_B(t)$ deve ser um polinômio primitivo, sendo ${\varphi }_B(t)$ o polinômio característico de

$B=\left(\begin{array}{ccccc}0& I_w& \cdots & 0& 0\\ ⋮& & & & \\ I_w& ⋮& \ddots & ⋮& ⋮\\ ⋮& & & & \\ 0& 0& \cdots & I_w& 0\\ 0& 0& \cdots & 0& I_{w-r}\\ S& 0& \cdots & 0& 0\end{array}\right)\begin{array}{c}\\ \\ \leftarrow m\text{-ésima linha}\\ \\ \\ \end{array}$

$S=\left(\begin{array}{cc}0& I_r\\ I_{w-r}& 0\end{array}\right)A$

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 $2^{nw-r}-1$ (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. Também foi desenvolvida por Matsumoto e Nishimura, em conjunto com Mariko Hagita e Mutsuo Saito. Foi submetida ao projeto eSTREAM da rede eCRYPT. 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. 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×10⁷ inteiros aleatórios de 32 bits.

O SFMT (Mersenne Twister rápido orientado a SIMD) é uma variante do Mersenne Twister, introduzida em 2006, projetado para ser rápida quando executada em SIMDs de 128 bits.

• É quase duas vezes mais rápido que o Mersenne Twister.
• 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 ⁶⁰⁷ − 1 a 2 ²¹⁶⁰⁹¹ − 1.

Intel SSE2 e PowerPC AltiVec utilizam a variante SFMT, que também é usada para jogos com o Cell BE no PlayStation 3.

TinyMT é uma variante do Mersenne Twister, proposto por Saito e Matsumoto em 2011. 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 $2^{127}-1$, 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.
• Um período muito longo de $2^{19937}-1$ . Observe que um longo período não é garantia de qualidade em um gerador de números aleatórios, períodos curtos, como o $2^{32}$ comum em muitos pacotes de software mais antigos, pode ser problemático.
• 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.

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.
• Exibe duas falhas claras (complexidade linear) tanto no Crush quanto no BigCrush no conjunto TestU01. O teste, como o Mersenne Twister, é baseado em um ${\mathbf{\text{F}}}_2$ -álgebra.
• 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.
• 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. Diz-se que a versão GPU (MTGP) é ainda melhor.
• 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, IDL, R, Ruby, Free Pascal, PHP, Python (também disponível em NumPy, no entanto o padrão foi alterado para PCG64 a partir da versão 1.17 ), CMU Common Lisp, Embeddable Common Lisp, Steel Bank Common Lisp, 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)
• Bibliotecas e software do tipo Unix : GLib, GNU Multiple Precision Arithmetic Library, GNU Octave, GNU Scientific Library
• Outros: Microsoft Excel, GAUSS, gretl, Stata, SageMath, Scilab, Maple, MATLAB

Também está disponível no Apache Commons, na biblioteca C++ padrão (desde C++11 ), e no Mathematica. Implementações de complementos são fornecidas em muitas bibliotecas de programas, incluindo as Bibliotecas Boost C++, a Biblioteca CUDA, e a Biblioteca Numérica NAG.

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". Também é de igual maneira um dos PRNGs no SAS: os outros geradores estão presentes apenas pelo fator de compatibilidade. O Mersenne Twister é o PRNG padrão no Stata, o outro é o KISS, para compatibilidade com versões mais antigas do Stata.

Alternativas

O gerador WELL ("Well Equidistributed Long-period Linear"), oferece recuperação mais rápida, aleatoriedade igual e velocidade quase igual.

Geradores xorshift e variantes da Marsaglia são os mais rápidos na classe de LFSRs.

MELGs de 64 bits ("Geradores ${\mathbf{\text{F}}}_2$-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 .

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.

Leitura adicional

• Predefinição:Citation.
• Predefinição:Citation.

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