GENERADOR MULTIPLE RECURSIVO.

GENERADOR MULTIPLE RECURSIVO

Un generador múltiple recursivo se define por la expresión recursiva,

[pic 1]

donde el módulo m y el orden k son enteros positivos y cada pertenece al conjunto {0, 1, …, m-1}.[pic 2]

El generador múltiple recursivo es una extensión del generador congruencial multiplicativo donde se usan los valores del k anterior para generar el siguiente.

En la fórmula, se definen   como eneteros multiplicadores que existen entre 0 y , donde  es distinto a 0. Dado que las semillas ( son distintas a ccero, se sigue la fórmula recursiva para producir una secuencia de números aleatorios.[pic 3][pic 4][pic 5][pic 6]

El periodo de un generador múltiple recursivo es mucho mayor  que el de un generador congruencial multiplicativo. Se ha demostrado, que siendo “m” un primo, el período máximo de una generación  es de .[pic 7]

Los generadores múltiples recursivos usualmente necesitan muchas multiplicaciones y sumas en la solución de la fórmula dada, por lo cual aumenta enormemente el tiempo necesario para resolverse en los casos en que el módulo sea muy alto.

Por lo tanto, los generadores múltiples recursivos son considerados como poco eficientes a la hora de producir números en comparación con otros generadores más simples, que pueden utilizar menos recursos y menos tiempos con operaciones más cortas siendo usadas en sus respectivas fórmulas matemáticas. Es por esto que su uso práctico es muy limitado.

GENERADORES CONGRUENCIALES MATRICIALES

H. Niederreiter y M. Groethe,  sugirieron  una fórmula recursiva que envuelve multiplicaciones de matrices, y nombraron a las funciones como  Generadores Congruenciales Matriciales (Matrix Congruential Generators). La fórmula se enuncia de la siguiente manera:

[pic 8]

Donde x es un vector de enteros positivos, p es un módulo primo y es un vector dimensional distinto a cero.[pic 9]

Un generador congruencial matricial produce una secuencia de vectores con un período máximo de . Para calcular el siguiente vector de un generador congruencial matricial, se necesitan guardar los coeficientes matriciales, las semillas del vector y k x k enteros de la matriz. Poder determinar los coeficientes de la matriz A es muy intensivo para la CPU y sumamente difícil de calcular sin una ayuda externa.[pic 10]

Para mejorar la eficiencia de los generadores matriciales congruenciales, se diseñó una matriz multiplicadora especial que reemplaze a A en la fórmula. Se le llamó Generador Rápido Congruencial Matricial (Fast Matrix Congruential Generator). La matriz con la fórmula recursiva es la siguiente:

[pic 11]

Donde están los mismos valores, pero el rendimiento que tiene este método de generación es mayor al del generador congruencial matricial básico, y por lo tanto existe mayor eficiencia con los mismos resultados de salida.

GENERADOR DE REGISTRO DE DESPLAZAMIENTO CON RETROALIMENTACIÓN LINEAL

El generador de  registro de desplazamiento con retroalimentación lineal (linear feedback shift register), es un generador de números aleatorios propuesto por Robert C. Tausworthe en 1965, se basa en una secuencia binaria y se genera por medio de una recurrencia determinada por la formula:

[pic 12]

En donde todas las variables toman los valores de 0 o 1. Es similar al generador múltiple recursivo, con la diferencia de que los valores se representan como enteros binarios.

Para mejorar el rendimiento del generador, los valores de a deben ser cero. Teniendo un módulo de dos se puede dar una recurrencia superior para tener un periodo de vida óptimo.

El bit de entrada del generador es una función lineal de su  estado interior, comúnmente se utiliza la función de XOR, que sirve para crear la siguiente salida en el estado del generador.

En este generador, el valor inicial es la semilla, y al igual que en otros generadores, la salida de los valores que serán producidos por éste, serán determinados por los valores anteriores emitidos a su vez por la semilla. Eventualmente el generador entrará en un ciclo repetitivo de salidas y entradas, debido al número finito de estados posibles creados por el generador. Sin embargo, el generador de registro de desplazamiento con retroalimentación lineal puede producir una secuencia de bits que parecen completamente aleatorias y tienen un ciclo muy extenso.

El generador de registro de desplazamiento con retroalimentación lineal tiene múltiples aplicaciones como generador aleatorio gracias a su posible extenso ciclo de vida, y sus implementaciones son muy comunes en el ámbito digital, en hardware y software.

GENERADOR DE WICHMANN-HILL

El generador de Wichmann-Hill fue propuesto en el año 1982 por Brian Wichmann y David Hill. Es un ejemplo de generador combinado, y se basa en el uso simultáneo de tres generadores congruenciales lineales. El generador crea números entre 0.0 y 0.1 y se encuentra libre de relaciones entre los números y pasa las pruebas de aleatoriedad.

...