Tornado de Mersenne

ImprimirCitar

Generador de número de maniobra

El Mersenne Twister es un generador de números pseudoaleatorios (PRNG) de uso general desarrollado en 1997 por Makoto Matsumoto [ja] (松本眞 ) y Takuji Nishimura (西村拓士 ). Su nombre deriva del hecho de que la longitud de su período se elige como un primo de Mersenne.

El Mersenne Twister se diseñó específicamente para corregir la mayoría de los defectos que se encuentran en los PRNG más antiguos.

La versión más utilizada del algoritmo Mersenne Twister se basa en el Mersenne prime ${displaystyle 2^{19937}-1}$ . The standard implementation of that, MT19937, uses a 32-bit word length. Hay otra aplicación (con cinco variantes) que utiliza una longitud de palabra de 64 bits, MT19937-64; genera una secuencia diferente.

Solicitud

Software

El Mersenne Twister se utiliza como PRNG predeterminado por el siguiente software:

Idiomas de programación: Dyalog APL, IDL, R, Ruby, Free Pascal, PHP, Python (también disponible en NumPy, sin embargo el default fue cambiado a PCG64 en lugar de la versión 1.17), CMU Common Lisp, Embeddable Common Lisp, Steel Bank Common Lisp, Julia (hasta Julia 1.6 LTS, todavía disponible en más tarde, pero un RNG por defecto).
Bibliotecas y software de Linux: GLib, GNU Multiple Precision Arithmetic Library, GNU Octave, GNU Scientific Library.
Otros: Microsoft Excel, GAUSS, gretl, Stata. SageMath, Scilab, Maple, MATLAB.

También está disponible en Apache Commons, en la biblioteca estándar de C++ (desde C++11) y en Mathematica. Se proporcionan implementaciones complementarias en muchas bibliotecas de programas, incluidas las bibliotecas Boost C++, la biblioteca CUDA y la biblioteca numérica NAG.

El Mersenne Twister es uno de los dos PRNG en SPSS: el otro generador se mantiene solo por compatibilidad con programas más antiguos, y se afirma que el Mersenne Twister es "más confiable". El Mersenne Twister es igualmente uno de los PRNG en SAS: los otros generadores son más antiguos y obsoletos. El Mersenne Twister es el PRNG predeterminado en Stata, el otro es KISS, por compatibilidad con versiones anteriores de Stata.

Ventajas

Sin licencia y patente para todas las variantes excepto CryptMT.
Pasa numerosas pruebas para aleatoriedad estadística, incluyendo las pruebas Diehard y la mayoría, pero no todas las pruebas TestU01.
Un período muy largo ${displaystyle 2^{19937}-1}$ . Tenga en cuenta que aunque un largo período no es una garantía de calidad en un generador de números aleatorios, períodos cortos, como el $2^{32}$ común en muchos paquetes de software antiguos, puede ser problemático.
k-distribuido a la precisión de 32 bits para cada ${displaystyle 1leq kleq 623}$ (para una definición de k- Distribuido, véase abajo)
Las implementaciones generalmente crean números aleatorios más rápido que los métodos implementados por hardware. Un estudio encontró que el Mersenne Twister crea números aleatorios de puntos flotantes de 64 bits aproximadamente veinte veces más rápido que el conjunto de instrucciones RDRAND basadas en hardware.

Desventajas

Búfer de estado relativamente grande, de 2,5 KiB, a menos que se utilice la variante TinyMT (discutida abajo).
Mediacre mediante estándares modernos, a menos que se utilice la variante SFMT (discutida abajo).
Exhibe dos fallos claros (complejidad lineal) tanto en Crush como BigCrush en la suite TestU01. La prueba, como Mersenne Twister, se basa en un ${displaystyle {textbf {F}}_{2}}$ - álgebra. Hay varios otros generadores que pasan todas las pruebas (y numerosos generadores que fallan mal).
Múltiples instancias que difieren sólo en el valor de semilla (pero no otros parámetros) no son generalmente apropiadas para simulaciones Monte-Carlo que requieren generadores de números aleatorios independientes, aunque existe un método para elegir múltiples conjuntos de valores de parámetro.
Difusión deficiente: puede tomar mucho tiempo para comenzar a generar salida que pasa pruebas de aleatoriedad, si el estado inicial es altamente no-religente, especialmente si el estado inicial tiene muchos ceros. Una consecuencia de esto es que dos instancias del generador, iniciadas con estados iniciales que son casi iguales, producirán generalmente casi la misma secuencia para muchas iteraciones, antes de eventualmente divergir. La actualización de 2002 al algoritmo MT ha mejorado la inicialización, de modo que comenzar con tal estado es muy poco probable. Se dice que la versión GPU (MTGP) es aún mejor.
Contiene subsecuencias con más 0's que 1's. Esto se suma a la mala propiedad de la difusión para hacer difícil la recuperación de muchos estados cero.
No es criptográficamente seguro, a menos que se utilice la variante CryptMT (discutida abajo). La razón es que observar un número suficiente de iteraciones (624 en el caso de MT19937, ya que este es el tamaño del vector estatal del que se producen las iteraciones futuras) permite predecir todas las iteraciones futuras.

Alternativas

Un generador alternativo, WELL ("Lineal de período largo bien equidistribuido"), ofrece una recuperación más rápida, la misma aleatoriedad y una velocidad casi igual.

Los generadores xorshift y las variantes de Marsaglia son los más rápidos en la clase de LFSR.

64-bit MELGs ("64-bit Maximally Equidistributed ${displaystyle {textbf {F}}_{2}}$ -Linear Generators with Mersenne Prime Período") están completamente optimizados en términos del k- Propiedades de distribución.

La familia ACORN (publicada en 1989) es otro PRNG distribuido por k, que muestra una velocidad computacional similar a la de MT y mejores propiedades estadísticas, ya que cumple con todos los criterios TestU01 actuales (2019); cuando se usa con opciones apropiadas de parámetros, ACORN puede tener un período y una precisión arbitrariamente largos.

La familia PCG es un generador de período largo más moderno, con una mejor localidad de caché y un sesgo menos detectable utilizando métodos de análisis modernos.

Distribución K

Una secuencia de pseudoprensa $x_{i}$ de w-bit enteros de período P se dice que k-distribuido a v- precisión de bits si el siguiente sostiene.

Deja que trunc_v()x) denota el número formado por el líder v bits of x, y considerar P de la k v-bit vectores

<math alttext="{displaystyle (operatorname {trunc} _{v}(x_{i}),operatorname {trunc} _{v}(x_{i+1}),,ldotsoperatorname {trunc} _{v}(x_{i+k-1}))quad (0leq i()truncv⁡ ⁡ ()xi),truncv⁡ ⁡ ()xi+1),...... ,truncv⁡ ⁡ ()xi+k− − 1))()0≤ ≤ i.P){displaystyle (operatorname {trunc} _{v}(x_{i}),operatorname {trunc} _{v}(x_{i+1}),,ldotsoperatorname {trunc} _{v}(x_{i+k-1})})quad (0leq i done)}}}<img alt="{displaystyle (operatorname {trunc} _{v}(x_{i}),operatorname {trunc} _{v}(x_{i+1}),,ldotsoperatorname {trunc} _{v}(x_{i+k-1}))quad (0leq i.

Entonces cada uno de los

{displaystyle 2^{kv}}

posibles combinaciones de bits ocurren el mismo número de veces en un período, excepto por la combinación de todo cero que ocurre una vez menos a menudo.

Detalle algorítmico

Visualización de generación de enteros pseudo-aleatorios de 32 bits usando un Twister Mersenne. La sección "Número extra" muestra un ejemplo donde el entero 0 ya ha sido la salida y el índice está en entero 1. 'Números de origen' se ejecuta cuando todos los enteros han sido de salida.

Para un w- bit word length, el Mersenne Twister genera enteros en el rango ${displaystyle [0,2^{w}-1]}$ .

El algoritmo Mersenne Twister se basa en una recurrencia lineal de matriz sobre un campo binario finito ${displaystyle {textbf {F}}_{2}}$ . El algoritmo es un registro de cambios de retroalimentación generalizado retorcido (GFSR girado, o TGFSR) de forma normal racional (TGFSR(R)), con reflexión y temperamento del estado. La idea básica es definir una serie $x_{i}$ a través de una simple relación de recurrencia, y luego números de salida de la forma ${displaystyle x_{i}^{T}}$ , donde T es un invertido ${displaystyle {textbf {F}}_{2}}$ -Matrix llamó una matriz templada.

El algoritmo general se caracteriza por las siguientes cantidades (algunas de estas explicaciones tienen sentido solo después de leer el resto del algoritmo):

w: tamaño de la palabra (en número de bits)
n: grado de recurrencia
m: palabra media, un offset utilizado en la relación recurrencia que define la serie $x$ , $<math alttext="{displaystyle 1leq m1\leq \leq m.n{displaystyle 1leq m won} <img alt="{displaystyle 1leq m$
r: punto de separación de una palabra, o el número de bits del bitmask inferior, ${displaystyle 0leq rleq w-1}$
a: coeficientes de la matriz de giro de forma normal racional
b, c: TGFSR(R) mordiscos templados
s, t: TGFSR(R) cambio de bit templado
u, d, l: adicional Mersenne Twister templado cambios de bits / máscaras

con la restricción ${displaystyle 2^{nw-r}-1}$ es una prima Mersenne. Esta opción simplifica la prueba de primitividad y k-distribución que se necesitan en la búsqueda del parámetro.

La serie $x$ se define como una serie de w- cantidades de bits con relación de recurrencia:

{displaystyle x_{k+n}:=x_{k+m}oplus left(({x_{k}}^{u}mid {x_{k+1}}^{l})Aright)qquad k=0,1,ldots }

Donde $mid$ denota concatenación de vectores de bits (con bits superiores a la izquierda), ${displaystyle oplus }$ el bitwise exclusivo o (XOR), ${displaystyle x_{k}^{u}}$ significa la parte superior w − r bits of ${displaystyle x_{k}}$ , y ${displaystyle x_{k+1}^{l}}$ significa el menor r bits of ${displaystyle x_{k+1}}$ . La transformación del giro A se define en la forma normal racional como:

{displaystyle A={begin{pmatrix}0&I_{w-1}\a_{w-1}&(a_{w-2},ldotsa_{0})end{pmatrix}}}

{displaystyle I_{w-1}}

{displaystyle (w-1)(w-1)}

{displaystyle {textbf {F}}_{2}}

{displaystyle {boldsymbol {x}}A={begin{cases}{boldsymbol {x}}gg 1&x_{0}=0\({boldsymbol {x}}gg 1)oplus {boldsymbol {a}}&x_{0}=1end{cases}}}

{displaystyle x_{0}}

{displaystyle x}

Como TGFSR(R), la Mersenne Twister es cascada con una transformación templada para compensar la reducida dimensionalidad de la equidistribución (por la elección de la A estar en la forma normal racional). Note que esto es equivalente al uso de la matriz A Donde ${displaystyle A=T^{-1}*AT}$ para T una matriz invertible, y por lo tanto el análisis del polinomio característico mencionado a continuación todavía sostiene.

Al igual que con A, elegimos una transformación de templado para que sea fácilmente computable y, por lo tanto, en realidad no construimos T en sí mismo. El templado se define en el caso de Mersenne Twister como

{displaystyle {begin{aligned}y&equiv xoplus ((xgg u)~And ~d)\y&equiv yoplus ((yll s)~And ~b)\y&equiv yoplus ((yll t)~And ~c)\z&equiv yoplus (ygg l)end{aligned}}}

Donde $x$ es el siguiente valor de la serie, $y$ es un valor intermedio temporal, y $z$ es el valor devuelto del algoritmo, con $ll$ y $gg$ como el bitwise izquierda y derecha turnos, y $&$ como el bitwise AND. Las transformaciones primera y última se añaden con el fin de mejorar la distribución de bit inferior. De la propiedad de TGFSR, ${displaystyle s+tgeq lfloor {frac {w}{2}}rfloor -1}$ se requiere para alcanzar el límite superior de la distribución de los bits superiores.

Los coeficientes para MT19937 son:

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

Tenga en cuenta que las implementaciones de 32 bits de Mersenne Twister generalmente tienen d = FFFFFFFF₁₆. Como resultado, la d ocasionalmente se omite de la descripción del algoritmo, ya que bitwise y con d en ese caso no tiene efecto.

Los coeficientes para MT19937-64 son:

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

Inicialización

El estado necesario para una implementación de Mersenne Twister es una variedad de n valores de w cada uno. Para inicializar el array, un w- valor de semilla bit se utiliza para suministrar $x_{0}$ a través de $x_{n-1}$ por configuración $x_{0}$ al valor de la semilla y, posteriormente,

{displaystyle x_{i}=ftimes (x_{i-1}oplus (x_{i-1}gg (w-2)))+i}

para $i$ desde $1$ a $n-1$ .

El primer valor que genera el algoritmo se basa en $x_{n}$ , no en $x_{0}$ .
La constante f forma otro parámetro al generador, aunque no parte del algoritmo adecuado.
El valor para f para MT19937 es 1812433253.
El valor para f para MT19937-64 es 6364136223846793005.

Comparación con GFSR clásico

Para lograr el ${displaystyle 2^{nw-r}-1}$ límite superior teórico del período en un TGFSR, ${displaystyle phi _{B}(t)}$ debe ser un polinomio primitivo, ${displaystyle phi _{B}(t)}$ ser el polinomio característico

{displaystyle B={begin{pmatrix}0&I_{w}&cdots &0&0\vdots &&&&\I_{w}&vdots &ddots &vdots &vdots \vdots &&&&\0&0&cdots &I_{w}&0\0&0&cdots &0&I_{w-r}\S&0&cdots &0&0end{pmatrix}}{begin{matrix}\\leftarrow m{text{-th row}}\\\\end{matrix}}}

{displaystyle S={begin{pmatrix}0&I_{r}\I_{w-r}&0end{pmatrix}}A}

La transformación de torsión mejora el GFSR clásico con las siguientes propiedades clave:

El período alcanza el límite superior teórico ${displaystyle 2^{nw-r}-1}$ (excepto si se inicializa con 0)
Equidistribución en n dimensiones (por ejemplo, generadores congruenciales lineales pueden gestionar mejor la distribución razonable en cinco dimensiones)

Pseudocódigo

El siguiente pseudocódigo implementa el algoritmo general Mersenne Twister. Las constantes w, n, m, r, a, u, d, s, b, t, c, l y f son como en la descripción del algoritmo anterior. Se supone que int representa un tipo suficiente para contener valores con bits w:

 // Crear una longitud n matriz para almacenar el estado del generador int[0..n-1] MT
 int índice:= n+ 1
 const int inferior_mask = (1) r- 1 // Es decir, el número binario de r 1's const int superior_mask = más bajo w bits of (no inferior_mask)

 // Iniciar el generador de una semilla función seed_mt(int simiente) {
índice:= nMT[0]:= semillas
 para i desde 1 a ()n - 1) { // bucle sobre cada elementoMT[i]:= más bajo w bits of (f * (MT[i-1) xor (MT[i-1] ()w-2)) + i)
}
}

 // Extraer un valor templado basado en MT[index] // llamando a giro() cada uno n números función extract_number() {}
 si indice n {}
 si indexación n {}
 error "El generador nunca fue sembrado"
 // Alternativamente, semilla con valor constante; 5489 se utiliza en el código de referencia C}
twist()
}

 int y:= MT[index]
Y... Sí. xor (y u) y d)
Y... Sí. xor (y s) y b)
Y... Sí. xor (y t) y c)
Y... Sí. xor (y l)

índice:= índice + 1
 retorno más bajo w bits of (y)
}

 // Generar el siguiente n valores de la serie x_i función giro() {
 para i desde 0 a ()n-1) {
 int x:= (MT[i) y superior_mask)
confidencialidad (MT[(i+1) mod n] y inferior_mask)
 int xA:= x > 1
 si (x mod 2) != 0 // bit más bajo de x es 1xA:= xA xor a}
MT[i]:= MT[i + m) mod n] xor xA
}
índice:= 0
}

Variantes

CryptMT

CryptMT es un cifrado de flujo y un generador de números pseudoaleatorios criptográficamente seguro que utiliza internamente Mersenne Twister. Fue desarrollado por Matsumoto y Nishimura junto con Mariko Hagita y Mutsuo Saito. Ha sido presentado al proyecto eSTREAM de la red eCRYPT. A diferencia de Mersenne Twister o sus otros derivados, CryptMT está patentado.

MTGP

MTGP es una variante de Mersenne Twister optimizada para unidades de procesamiento de gráficos publicada por Mutsuo Saito y Makoto Matsumoto. Las operaciones básicas de recurrencia lineal se extienden desde MT y los parámetros se eligen para permitir que muchos subprocesos calculen la recurrencia en paralelo, mientras comparten su espacio de estado para reducir la carga de memoria. El documento afirma que se mejoró la equidistribución sobre MT y el rendimiento en una GPU muy antigua (Nvidia GTX260 con 192 núcleos) de 4,7 ms para 5 × 10⁷ enteros aleatorios de 32 bits.

SFMT

El SFMT (Fast Mersenne Twister orientado a SIMD) es una variante de Mersenne Twister, introducido en 2006, diseñado para ser rápido cuando se ejecuta en SIMD de 128 bits.

Es aproximadamente el doble de rápido que Mersenne Twister.
Tiene una mejor propiedad de equidistribución de la precisión v-bit que MT pero peor que WELL ("Well Equidistributed Long-period Linear").
Tiene una recuperación más rápida del estado inicial de cero-exceso que MT, pero más lenta que WELL.
Soporta varios períodos de 2⁶⁰⁷− 1 a 2²¹⁶⁰⁹¹− 1.

Intel SSE2 y PowerPC AltiVec son compatibles con SFMT. También se usa para juegos con Cell BE en PlayStation 3.

TinyMT

Tiny MT es una variante de Mersenne Twister, propuesta por Saito y Matsumoto en 2011. Tiny MT utiliza sólo 127 bits de espacio estatal, una disminución significativa en comparación con el original de 2,5 KiB de estado. Sin embargo, tiene un período de ${displaystyle 2^{127}-1}$ , mucho más corto que el original, por lo que sólo es recomendado por los autores en los casos en que la memoria es una prima.

Contenido relacionado

Más resultados...