Tipos de Generadores de Numeros Aleatorios

Mersenne twister

El Mersenne twister es un Generador de números pseudoaleatorios desarrollado en 1997 por Makoto Matsumoto y Takuji Nishimura  reputado por su calidad.

Su nombre proviene del hecho de que la longitud del periodo corresponde a un Número primo de Mersenne. Existen al menos dos variantes de este algoritmo, distinguiéndose únicamente en el tamaño de primos Mersenne utilizados. El más reciente y más utilizado es el Mersenne Twister MT19937, con un tamaño de palabra de 32-bit.

La parte entera del algoritmo de Twister de Mersenne no implica ninguna aritmética en el sentido de suma, resta, multiplicación o división. Todas las operaciones son turnos, y, o, y xor.

Todos los elementos del estado, excepto el último, son enteros aleatorios de 32 bits sin signo que forman un caché que se genera cuidadosamente al inicio. Esta generación se desencadena por una semilla, un entero único que inicia todo el proceso.

El último elemento del estado es un puntero al caché. Cada solicitud de un entero aleatorio hace que un elemento se retire de la memoria caché y el puntero se incremente. Cuando el puntero llega al final de la memoria caché, la memoria caché se rellena con otros 623 elementos.

El algoritmo se analiza investigando las propiedades teóricas de grupo de las operaciones de permutación y atemperación. Los parámetros se han elegido para que el período sea un primo de Mersenne 2 ^ 19937-1. Este período es mucho más largo que cualquier otro generador de números aleatorios propuesto antes o después y es una de las razones de la popularidad de MT.

Por diseño, los resultados generados satisfacen una propiedad de equidistribución en un cubo de 623 dimensiones.

MRG32K3a

MRG32K3a o también conocido como L’Ecuyer es un generador de números aleatorios multiple recursivo, el cual se basa en la siguiente formula

Este es un generador recursivo múltiple combinado de 32 bits con dos componentes de orden 3:

Debemos definir el vector inicial [pic 1]

[pic 2]

[pic 3]

[pic 4]

[pic 5]

El generador combinado MRG32k3a cumple con los requisitos para los RNG modernos, como una buena uniformidad multidimensional o un período prolongado.

Tiene un periodo: [pic 6]

MWC o Multiplicación por Acarreo

En ciencias de la computación, la multiplicación con acarreo (MWC de las siglas en inglés de multiply-with-carry) es un método creado por George Marsaglia para generar secuencias de números enteros aleatorios basados en un conjunto inicial de dos a miles de valores semilla seleccionados aleatoriamente. Las principales ventajas del método MWC son que usa simple aritmética computacional de enteros y produce una rápida generación de secuencias de números aleatorios con términos de gran tamaño, dentro del rango aproximado de 260 a 22,000,000.

Al igual que sucede con la mayoría de los generadores de números pseudoaleatorios, las secuencias resultantes están en función de los valores semilla seleccionados aleatoriamente.

Una secuencia MWC está basada en un módulo de aritmética en base b, usualmente b = 232, dado que dicho módulo en base b es automático en muchas computadoras. Sin embargo, a veces es usada una base b = 232 − 1, porque la aritmética para módulos 232 − 1 requiere solamente un ajuste simple hacia 232, y la teoría para las secuencia MWC basadas en módulos 232 presenta algunas dificultades muy molestas que pueden ser evitadas usando b = 232 − 1. En su forma más común, un generador lag-r MWC requiere una base b, un multiplicador a, y un conjunto de r+1 valores semilla aleatorios, consistente en r residuos de b,

[pic 7]

y un acarreo inicial [pic 8]

La secuencia lag-r MWC es entonces una secuencia de pares xn, cn determinada por

[pic 9]

y la salida del generador MWC es la secuencia de x's,

[pic 10]

El período de un generador lag-r MWC es el orden de b en el grupo multiplicativo de números módulo abr − 1. Es habitual escoger a tal que p = abr − 1 es un primo para el cual el orden de b puede ser determinado. Ya que 2 es un residuo cuadrático de números de la forma 8k±1, b = 232 no puede ser una raíz primitiva de p = abr − 1. Por consiguiente no hay generadores MWC en base 232 que presentan el período máximo posible, una de las dificultades que el uso de b = 232 − 1 supera.[pic 11]

KISS

KISS (Keep it Simple Stupid) es una familia de generadores de números pseudoaleatorios introducidos por George Marsaglia. Todos los generadores KISS combinan tres o cuatro generadores de números aleatorios independientes con el objetivo de mejorar la calidad de la aleatoriedad. Los generadores KISS producen enteros aleatorios de 32 bits o 64 bits, a partir de los cuales se pueden construir números aleatorios de coma flotante si se desea.

El generador original de 1993 se basa en la combinación de un generador congruente lineal y de dos generadores de registro de desplazamiento de retroalimentación lineales. Tiene un período de 295.

KISS consiste en una combinación de cuatro subgeneradores, cada uno con 32 bits de estado, de tres tipos:

- un generador congruente lineal módulo 232

- un generador lineal binario general sobre el espacio vectorial GF (2) 32

- dos generadores multiply-with-carry módulo 216, con diferentes parámetros

Los cuatro generadores se actualizan independientemente, y sus estados se combinan para formar una secuencia de palabras de salida de 32 bits. Las cuatro variables de estado se tratan como palabras de 32 bits sin signo.

El generador KISS, (Keep It Simple Stupid), está diseñado para combinar los dos generadores multiply-with-carry en MWC con el registro de 3 cambios SHR3 y el generador congruente CONG, usando addition y exclusive-or. Período alrededor de   2 ^ 123.

[pic 12]

LFIB4

Un generador de Fibonacci retardado (LFG o, a veces, LFib) es un ejemplo de generador de números pseudoaleatorios. Esta clase de generador de números aleatorios tiene como objetivo ser una mejora en el generador congruente lineal "estándar". Estos se basan en una generalización de la secuencia de Fibonacci.

...