LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

El Mersenne Twister es un generador de números pseudoaleatorios (PRNG). Es, con mucho, el PRNG de uso general más ampliamente utilizado. ^[1] Su nombre se deriva del hecho de que la duración de su período se elige para ser una prima de Mersenne .

El Mersenne Twister fue desarrollado en 1997 por Makoto Matsumoto  [ ja ] ( 松本 眞 ) y Takuji Nishimura ( 西村 拓 士 ) . ^[2] Fue diseñado específicamente para corregir la mayoría de los defectos encontrados en PRNG más antiguos.

La versión más utilizada del algoritmo Mersenne Twister se basa en el Mersenne prime 2 ¹⁹⁹³⁷ −1. La implementación estándar de eso, MT19937, utiliza una longitud de palabra de 32 bits . Hay otra implementación que utiliza una longitud de palabra de 64 bits, MT19937-64; genera una secuencia diferente.

Adopción en sistemas de software [ editar ]

El Mersenne Twister es el PRNG predeterminado para los siguientes sistemas de software: Microsoft Excel , ^[3]GAUSS , ^[4] GLib , ^[5] Biblioteca de aritmética de precisión múltiple de GNU , ^[6] Octava de GNU , ^[7] Biblioteca científica de GNU , ^{[8] ]} gretl , ^[9] IDL , ^[10] Julia , ^[11] CMU Common Lisp , ^[12] Embeddable Common Lisp , ^[13]Steel Bank Common Lisp , ^[14] Maple , ^[15] MATLAB, ^[16] Free Pascal , ^[17] PHP , ^[18] Python , ^[19] [20] R , ^[21] Ruby, ^[22] SageMath , ^[23] Scilab , ^[24] Stata . ^[25]

También está disponible en Apache Commons , ^[26] en C ++ estándar (desde C ++ 11 ), ^[27] [28] y en Mathematica. ^[29] Las implementaciones adicionales se proporcionan en muchas bibliotecas de programas, incluidas las bibliotecas Boost C ++ , ^[30] la biblioteca CUDA , ^[31] y la biblioteca numérica NAG . ^[32]

El Mersenne Twister es uno de los dos PRNG en SPSS : el otro generador se mantiene solo por compatibilidad con los programas más antiguos, y se dice que el Mersenne Twister es "más confiable". ^[33] Mersenne Twister es, de manera similar, uno de los PRNG en SAS : los otros generadores son más antiguos y están en desuso. ^[34]

Ventajas [ editar ]

• Con licencia permisiva y sin patentes para todas las variantes, excepto CryptMT.
• Pasa numerosas pruebas de aleatoriedad estadística, incluidas las pruebas de Diehard y la mayoría, pero no todas, de las pruebas de TestU01 . ^[35]
• Un período muy largo de 2 ¹⁹⁹³⁷  - 1. Tenga en cuenta que si bien un período largo no es una garantía de calidad en un generador de números aleatorios, los períodos cortos, como los 2 ³² comunes en muchos paquetes de software más antiguos, pueden ser problemáticos. ^[36]
• k -distribuido a una precisión de 32 bits por cada 1 ≤ k ≤ 623 (para una definición de k -distribuido, ver más abajo)
• Las implementaciones generalmente crean números aleatorios más rápido que otros métodos. Un estudio encontró que el Mersenne Twister crea números aleatorios de punto flotante de 64 bits aproximadamente veinte veces más rápido que el conjunto de instrucciones RdRand basado en procesador y implementado en hardware . ^[37]

Desventajas [ editar ]

• Búfer de estado relativamente grande, de 2.5 KiB , a menos que se use la variante TinyMT (que se describe a continuación).
• Rendimiento mediocre según los estándares modernos, ^{[38] a} menos que se use la variante SFMT (que se describe a continuación).
• Las instancias múltiples que difieren solo en el valor inicial (pero no en otros parámetros) generalmente no son apropiadas para simulaciones de Monte-Carlo que requieren generadores de números aleatorios independientes, aunque existe un método para elegir múltiples conjuntos de valores de parámetros. ^[39] [40]
• Puede tomar mucho tiempo comenzar a generar resultados que pasan pruebas de aleatoriedad , si el estado inicial es altamente no aleatorio, 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, generalmente emitirán casi la misma secuencia para muchas iteraciones, antes de que finalmente se desvíen. La actualización de 2002 del algoritmo MT ha mejorado la inicialización, por lo que es muy poco probable que comience con tal estado. ^[41]
• No es criptográficamente seguro , a menos que se use la variante CryptMT (que se describe a continuación). La razón es que la observación de un número suficiente de iteraciones (624 en el caso de MT19937, dado que este es el tamaño del vector de estado a partir del cual se producen las futuras iteraciones) permite predecir todas las iteraciones futuras.

Alternativas [ editar ]

Un generador alternativo, WELL ("Linea lineal de período largo bien equidistribuido"), ofrece una recuperación más rápida, una aleatoriedad igual y una velocidad casi igual. ^[42] Los generadores xorshift de Marsaglia y sus variantes son los más rápidos en esta clase. ^[43]

k -distribucion [ editar ]

Una secuencia pseudoaleatoria x _i de w -bit enteros del período P se dice que está distribuida en k con una precisión de v- bit si se cumple lo siguiente.

Deje trunc _v (x) denotan el número formado por los principales v bits de x , y considerar P de los k v vectores -bit

{\ displaystyle ({\ text {trunc}} _ {v} (x_ {i}), \, {\ text {trunc}} _ {v} (x_ {i + 1}), \, ..., \, {\ text {trunc}} _ {v} (x_ {i + k-1})) \ quad (0 \ leq i

.

Entonces, cada una de las 2 ^kv posibles combinaciones de bits ocurre el mismo número de veces en un período, excepto por la combinación de todo cero que ocurre una vez con menos frecuencia.

Detalle algorítmico [ editar ]

Visualización de la generación de enteros pseudoaleatorios de 32 bits utilizando un Mersenne Twister. La sección 'Extraer número' muestra un ejemplo donde el entero 0 ya se ha emitido y el índice está en el entero 1. 'Generar números' se ejecuta cuando todos los enteros se han generado.

Para una longitud de palabra de w- bit, el Mersenne Twister genera enteros en el rango [0, 2 ^w −1].

El algoritmo de Mersenne Twister se basa en una recurrencia lineal de matriz sobre un campo binario finito F ₂ . El algoritmo es un registro de desplazamiento de retroalimentación generalizado trenzado ^[44] (GFSR torcido, o TGFSR) de forma normal racional (TGFSR (R)), con reflexión de bits de estado y templado. La idea básica es definir una serie. $${\ displaystyle x_ {i}} a través de una relación de recurrencia simple, y luego los números de salida de la forma $${\ displaystyle x_ {i} T}, dónde $${\ displaystyle T}es un invertible F ₂ matriz llamada matriz de templado .

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

• w : tamaño de palabra (en número de bits)
• n : grado de recurrencia
• m : palabra media, un desplazamiento utilizado en la relación de recurrencia que define la serie x , 1 ≤ m < n
• r : punto de separación de una palabra, o el número de bits de la máscara de bits inferior, 0 ≤ r ≤ w - 1
• a : coeficientes de la matriz de torsión de forma normal racional
• b , c : Máscara de bits de temple TGFSR (R)
• s , t : cambios de bit de revenido TGFSR (R)
• u , d , l : cambios / máscaras adicionales de broca de templado Mersenne Twister

con la restricción de que 2 ^nw  -  r  - 1 es un primo de Mersenne. Esta opción simplifica la prueba de primitividad y la prueba de distribución k que se necesitan en la búsqueda de parámetros.

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

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

dónde $${\ displaystyle \ mid \ mid}denota la concatenación de vectores de bits (con los bits superiores a la izquierda),$${\ displaystyle \ oplus}el bitwise exclusivo o (XOR),$${\ displaystyle {x_ {k}} ^ {u}} significa la parte superior $${\ displaystyle wr} pedazos de $${\ displaystyle x_ {k}}y $${\ displaystyle x_ {k + 1} ^ {l}} significa el más bajo $${\ displaystyle r} pedazos de $${\ displaystyle x_ {k + 1}}. La transformación de giro A se define en forma normal racional como:

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

con I _{n  - 1} como la  matriz de identidad ( n  - 1) × ( n - 1). La forma normal racional tiene el beneficio de que la multiplicación por A se puede expresar de manera eficiente como: (recuerde que aquí la multiplicación de matrices se realiza en F ₂ y, por lo tanto, XOR a nivel de bit ocupa el lugar de la adición)

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

donde x ₀ es el bit de orden más bajo de x .

Al igual que TGFSR (R), el Mersenne Twister está en cascada con una transformada de temple para compensar la reducida dimensionalidad de la equidistribución (debido a la elección de que A esté en la forma racional normal). Tenga en cuenta que esto es equivalente a usar la matriz$${\ displaystyle A} dónde $${\ displaystyle A = T ^ {- 1} AT} para $${\ displaystyle T} una matriz invertible y, por lo tanto, el análisis del polinomio característico mencionado a continuación sigue siendo válido.

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

y  : = x  ⊕ (( x  >>  u ) &  d )

y  : = y  ⊕ (( y  <<  s ) &  b )

y  : = y  ⊕ (( y  <<  t ) &  c )

z  : = y  ⊕ ( y  >>  l )

donde x es el siguiente valor de la serie, y un valor intermedio temporal, z el valor devuelto por el algoritmo, con <<, >> como desplazamiento a la izquierda y derecha a nivel de bits, y & como a modo de bits y . La primera y la última transformación se agregan para mejorar la equidistribución de bits más bajos. Desde la propiedad de TGFSR,$${\ displaystyle s + t \ geq \ lfloor w / 2 \ rfloor -1} se requiere para alcanzar el límite superior de equidistribución para los bits superiores.

Los coeficientes para MT19937 son:

• ( w , n , m , r ) = (32, 624, 397, 31)
• a  = 9908B0DF ₁₆
• ( u , d ) = (11, FFFFFFFF ₁₆ )
• ( s , b ) = (7, 9D2C5680 ₁₆ )
• ( t , c ) = (15, EFC60000 ₁₆ )
• l  = 18

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

Los coeficientes para MT19937-64 son: ^[45]

• ( w , n , m , r ) = (64, 312, 156, 31)
• a  = B5026F5AA96619E9 ₁₆
• ( u , d ) = (29, 5555555555555555 ₁₆ )
• ( s , b ) = (17, 71D67FFFEDA60000 ₁₆ )
• ( t , c ) = (37, FFF7EEE000000000 ₁₆ )
• l  = 43

Inicialización [ editar ]

Como debe ser evidente a partir de la descripción anterior, el estado necesario para una implementación de Mersenne Twister es una matriz de n valores de w bits cada uno. Para inicializar la matriz, se utiliza un valor semilla de w- bit para suministrar x _{0 a} través de x _{n  - 1} estableciendo x ₀ en el valor semilla y luego configurando

x _i = f × ( x _i −1 ⊕ ( x _i −1 >> ( w −2))) + i

para i de 1 a n −1. El primer valor que luego genera el algoritmo se basa en x _n , no en x ₀ . La constante f forma otro parámetro para el generador, aunque no forma parte del algoritmo propiamente dicho. El valor para f para MT19937 es 1812433253 y para MT19937-64 es 6364136223846793005. ^[45]

Comparación con el GFSR clásico [ editar ]

Para alcanzar el  límite superior teórico 2 ^nw  -  r - 1 del período en un T GFSR , φ _B ( t ) debe ser un polinomio primitivo , siendo pol _B ( t ) el polinomio característico de

{\ displaystyle B = {\ begin {pmatrix} 0 & I_ {w} & \ cdots & 0 & 0 \\\ vdots &&&& \\ I_ {w} & \ vdots & \ ddots & \ vdots & \ vdots \\\ vdots &&&& \\ 0 & 0 & 0 & \ cdots & I_ {w} & 0 \\ 0 & 0 & \ cdots & 0 & I_ {wr} \\ S & 0 & \ cdots & 0 & 0 \ end {pmatrix}} {\ begin {matrix} \\\\\ leftarrow m {\ hbox {-th row}} \\\\\\\\\\ final {matriz}}}

{\ displaystyle S = {\ begin {pmatrix} 0 & I_ {r} \\ I_ {wr} & 0 \ end {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 2 ^nw  -  r  - 1 (excepto si se inicializa con 0)
• Distribución equitativa en n dimensiones (por ejemplo, los generadores lineales congruentes pueden, en el mejor de los casos, administrar una distribución razonable en cinco dimensiones)

Pseudocódigo [ editar ]

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

 // Crear una matriz n de longitud para almacenar el estado del generador 
 int [0 .. n -1] MT
  int index: = n +1
  const int lower_mask = (1 << r ) - 1 // Es decir, el binario número de r 1's 
 const int upper_mask = w bits más bajos de ( no lower_mask)
 
 // Inicializar el generador desde una 
 función de semilla seed_mt ( int seed) {
     índice: = n
     MT [0]: = semilla
     para i, de 1 a ( n - 1) { // bucle sobre cada elemento 
         MT [i]: = w bits más bajos de ( f * (MT [i-1] xor (MT [i-1] >> ( w - 2))) + i)
     }
 }
 
 // Extraiga un valor templado basado en MT [índice] 
 // llamando a twist () todos los n números 
 funcionan extract_number () {
      if index> = n {
          if index> n {
            error "El generador nunca se inicializó"
            // Alternativamente, inicialice con valor constante; 5489 se utiliza en el código de referencia C [46]
         }
         giro()
     }
 
     int y: = MT [índice]
     y: = y xor ((y >> u ) y  d )
     y: = y xor ((y << s ) y  b )
     y: = y xor ((y << t ) y  c )
     y: = y xor (y >> l )
 
     índice: = índice + 1
     devuelve los w bits más bajos de (y)
 }
 
 // Genere los siguientes n valores de la serie x_i 
 función twist () {
      para i de 0 a ( n -1) {
          int x: = (MT [i] y upper_mask)
                   + (MT [(i + 1) mod  n ] y lower_mask)
          int xA: = x >> 1
          if (x mod 2)! = 0 { // el bit más bajo de x es 1 
             xA: = xA xor  a
         }
         MT [i]: = MT [(i + m ) mod  n ] xor xA
     }
     índice: = 0
 }

Variantes [ editar ]

CryptMT [ editar ]

Artículo principal: CryptMT

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

MTGP [ editar ]

MTGP es una variante de Mersenne Twister optimizada para unidades de procesamiento de gráficos publicada por Mutsuo Saito y Makoto Matsumoto. ^[49] Las operaciones de recurrencia lineal básica se extienden desde MT y los parámetros se eligen para permitir que muchos subprocesos calculen la recursión en paralelo, mientras comparten su espacio de estado para reducir la carga de memoria. El documento afirma que la equidistribuciónmejorada en 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 [ editar ]

Esta sección necesita expansión. Puedes ayudar añadiéndolo . ( Junio ​​2007 )

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

• Es aproximadamente el doble de rápido que Mersenne Twister. ^[51]
• Tiene una mejor propiedad de equidistribución de v-bit de precisión que MT pero peor que WELL ("Lineal de periodo largo bien equidistribuido") .
• Tiene una recuperación más rápida del estado inicial sin exceso de cero que MT, pero más lento que WELL.
• Soporta varios periodos desde 2 ⁶⁰⁷ −1 hasta 2 ²¹⁶⁰⁹¹ −1.

Intel SSE2 y PowerPC AltiVec son compatibles con SFMT. También se usa para juegos con el Cell BE en la PlayStation 3 . ^[52]

TinyMT [ editar ]

TinyMT es una variante de Mersenne Twister, propuesta por Saito y Matsumoto en 2011. ^[53] TinyMT usa solo 127 bits de espacio de estado, una disminución significativa en comparación con los 2.5 KiB de estado del original. Sin embargo, tiene un período de 2 ¹²⁷ −1, mucho más corto que el original, por lo que los autores solo lo recomiendan en los casos en que la memoria es muy importante.