Teoria algoritmos congruenciales

Algoritmos congruenciales

Entre los algoritmos congruenciales se encuentran los algoritmos congruenciales lineales y los no lineales.  

Algoritmos congruenciales lineales

Los tipos de algoritmos congruenciales lineales que existen son el algoritmo congruencial lineal, el multiplicativo y el aditivo.  

Algoritmo Congruencial Lineal

Este algoritmo congruencial fue propuesto por D. H. Lehmer en 1955. Según Law y Kelton, este algoritmo ha sido el más utilizado. El algoritmo congruencial lineal genera una secuencia de números enteros por medio de la siguiente ecuación recursiva:

Xi+1 = (aXi + c) mod (m)

 Con i= 1, 2, 3, …, n

Donde X0 es la semilla, a es la constante multiplicativa, c es una constante aditiva y m es el módulo:X0 > 0, a > 0, c > 0 y m > 0 deben ser números enteros. La operación “mod m” significa multiplicar Xi por a, sumar c y dividir el resultado entre m para obtener el residuo Xi+1. Es importante señalar que la ecuación recursiva del algoritmo congruencial lineal genera una secuencia de números enteros y que para obtener números pseudo aleatorios en el intervalo (0, 1) se requiere de la siguiente ecuación:

[pic 1]

Con i= 1, 2, 3, …, n

Para que el algoritmo sea capaz de lograr el máximo período de vida n, es preciso que los parámetros X0, a, y m cumplan con ciertas condiciones. Banks, Carson, Nelson y Nicol sugieren lo siguiente: m debe ser múltiplo de 2g, donde g debe ser entero, a = 1+4k, donde k debe ser entero y c debe ser relativamente primo a m.

Bajo estas condiciones se obtiene un período de vida máximo: N=m=2g.

Algoritmo congruencial multiplicativo 

El algoritmo congruencial multiplicativo surge del algoritmo lineal cuando 0 =c. Entonces la ecuación recursiva es:

Xi+1 = (aXi) mod(m)

Con i= 1, 2, 3, …, n

En comparación con el algoritmo congruencial lineal, la ventaja del algoritmo multiplicativo es que implica una operación menos a realizar. Los parámetros de arranque de este algoritmo son X0, a y m, los cuales deben ser enteros y mayores que cero. Para transformar los números Xi en el intervalo (0, 1) se usa la ecuación:

[pic 2]

Con i = 1, 2, 3, …, n

De acuerdo con Banks, Carson, Nelson y Nicol, las condiciones que deben cumplir los parámetros para que el algoritmo congruencial multiplicativo alcance su máximo período son:

m debe ser múltiplo de 2g, donde g debe ser entero, a = 3+8k, donde k= 0, 1, 2, 3, …, X0 debe ser un número impar.

Bajo estas condiciones se logra un período de vida máximo: N= k/4= 2g-2.

Algoritmo congruencial aditivo

Este algoritmo requiere una secuencia previa de n números aleatorios X1, X2, X3, X4, …, Xn para generar una secuencia de números enteros que empiezan en Xn+1, Xn+2, Xn+3, Xn+4, …

Su ecuación recursiva es:

Xi = (Xi-1 + Xi-2) mod(m)

 Con I = n+1, n+2, n+3, …, N

[pic 3]

Algoritmos congruenciales no lineales

Dentro de los algoritmos congruenciales no lineales se tiene el algoritmo congruencial cuadrático y el de Blum, Blum, y Shub.

...