Métodos Congruenciales

Introducción

Los métodos congruenciales están basados en el algebra de congruencias. El objetivo de cada uno de estos métodos es la generación en un tiempo mínimo, de las sucesiones de números aleatorios con periodos máximos. Los métodos congruenciales son: El aditivo El multiplicativo El mixto.

Método Congruencial AditivoEs un método determinantico

que nos permite generar una serie de números pseudoaleatorios a partir de parámetros de arranque.

COMO FUNCIONA ?Este método requiere una secuencia previa de n

números enteros x1, x2 ,x3 ….xn para generar una nueva secuencia de números enteros que empiezan en xn+1,xn+2,xn+3…

Su ecuación recursiva es:Xi= (Xi-1 + Xi-n) mod(m) ; i=n+1,n+2,n+3,….,N Los numero ri se generan mediante la ecuación :

ri=xi/(m-1)

EJEMPLO: Generar 7 números pseudoaleatorios entre cero y uno a partir de la

siguiente secuencia de numero enteros: 65,89,98,03,69; m=100 . Sean x1=65 ,x2=89 ,x3=98 ,x4=03 ,x5=69. Generamos r1 ,r2 ,r3 ,r4 ,r5

,r6 ,r7. Generamos x6, x7,x8,x9,x10,x11,x12.

Solución: X6 =(x5+x1)mod100=(69+65)mod100=34 r1=34/99=0.3434 X7 =(x6+x2)mod100=(34+89)mod100=23 r2=23/99=0.2323 X8 =(x7+x3)mod100=(23+98)mod100=21 r3=21/99=0.2121 X9 =(x8+x4)mod100=(21+03)mod100=24 r4=24/99=0.2424 X10 =(x9+x5)mod100=(24+69)mod100=93 r5=93/99=0.9393 x11=(x10+x6)mod100=(93+34)mod100=27 r6=27/99=0.2727 x12=(x11+x7)mod100=(27+23)mod100=50 r7=50/99=0.5050

Método Congruencial MultiplicativoEste método es un caso especial de la

congruencia lineal cuando c=0, tenemos la siguiente formula: Xn+1= a.Xn (mod M).

Donde: a = Es la constante multiplicativa. m = Es la magnitud del módulo. X0 = Es la semilla.los requisitos mínimos que deben satisfacer los parámetros sonX0, a, m > 0; enteros y m > a, m >X0

Para una buena selección de los parametros inciales:

El valor de a = 8t +- 3 donde t es cualquier entero positivo.

El valor de m =2d, donde d es el número de bits de la palabra de la computadora.

Tómese X0 impar, relativamente primo a m.EJEMPLO 3. Desarrollar cinco iteraciones del generador Xn+1 = 3Xn mod 100, con X0=51....

xn rnd

51 0,51

53 0,53

59 0,59

77 0,77

31 0,31

Método Congruencial mixto o linealLos métodos congruenciales están

basados en el álgebra de congruencias.

El método mixto tiene la siguiente ecuación de recurrencia:

DONDEa = es la constante multiplicativa.c = es la constante aditiva.m = es la magnitud del módulo.X0 = es la semilla

Los requisitos mínimos que estos parámetros deben satisfacer son:X0, a, c, m >= 0; enteros y m > a, m > c, m > X0

Aquí mod representa a la operación aritmética módulo entre los enteros a y b tal que el resultado de (a mod b) es el residuo entero de la división a entre b.

SELECCIÓN DE LOS PARÁMETROS

SELECCIÓN DE m. Seleccionar m de modo que sea el número primo más grande posible y que a su vez sea menor que p, donde

SELECCION DE a. Preferentemente selecciónese a a de tal manera queI) (a-1) mod 4 = 0, si 4 es un factor de m.

II) (a-1) mod b = 0, si b es un factor primo de m. Usualmente, el valor de a se toma como a = 2k +1 ; k>=2 SELECCION DE c. Es recomendable escoger c tal

que c mod 8 = 5 SELECCION DE X0. La selección de X0 es irrelevante.

Ejemplo: Supongamos que se tiene un generador en el cual los valores de sus parámetros son: a = 5, c = 7, X0 = 4 y m = 8. El generador quedará de la siguiente manera: Xn+1 = (5 Xn + 7) mod 8.

Ventajas: utiliza poca memoria y es muy

rápido. fácil de volver a generar la misma

secuencia, guardando un solo número, (alcanza con partir desde la misma semilla: x0).

Desventajas: