ALGORITMOS CONGRUENCIALES:Lineales:

a) Algoritmo Lineal:

Este algoritmo fue propuesto por D.H. Lehmer en 1951. Genera una secuencia de números enteros por medio de esta ecuación recursiva:

Xi+1 = (aXi +C) mod (m) i=1,2,3,4…n

Donde:Xo = semilla, X0>0 y debe ser enteroa = constante multiplicativa a > 0 y entero.c = constante aditiva c>0 y entero.Mod m = modulo, significa realizar las operaciones anteriores y dividir el resultado entre el valor de m para obtener solamente el residuo.

Para convertir los números aleatorios generados, a números pseudo-aleatorios debemos realizar esta operación:

ri= Xim−1

CARACTERISTICAS Y CONDICIONES:

EJEMPLO

Para lograr el máximo periodo de vida n al algoritmo lineal es necesario que se cumplan las

siguientes condiciones:

m = 28

a = 1 + 4kk = enteroc = relativamente primo a ng = entero

Semilla X0 = 37a =19,c=33,mod=100

Xi+1 =(axi+c)mod(m) residuo X0 Ri = xi/m-1

X0=37 X=(19*37+33)/100 7.36 36 36/100-1 = 0.3636

X0=36 X=(19*36+33)/100 7.17 17 17/99=0.1717

X0=17 X=(19*17+33)/100 3.56 56 56/99=0.5656

X0=56 X=(19*56+33)/100 10.97 97 97/99=0.9797

ALGORITMOS CONGRUENCIALES:

b) Algoritmo multiplicativo:

Surge del algoritmo lineal cuando c = 0. Entonces la ecuación recursiva es:Xi+1 = (aXi) mod (m) i=0,1,2,3,4…n

Donde:Xo = semilla, X0>0 y debe ser enteroa = constante multiplicativa a > 0 y entero.Mod m = modulo, significa realizar las operaciones anteriores y dividir el resultado entre el valor de m para obtener solamente el residuo.

Para convertir los números aleatorios generados, a números pseudo-aleatorios debemos realizar esta operación:

ri= Xim−1

CARACTERISTICAS Y CONDICIONES:

EJEMPLO

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=n+8k,donde

k=0,1,2,3… , x0 y n debe ser un número impar.

Semilla X0 = 17k=2,g=5.

Xi+1 =(axi)mod(m)a = n+8k y m = 2g

X0 Ri = xi/m-1

X0=17,a=5+8(2),m=25 X=(21*17)mod(32) 5 5/32-1 = 0.1612

X0=5 X=(21*5)mod(32) 9 9/31=0.2903

X0=9 X=(21*9)mod(32) 29 29/31=0.9354

X0=29 X=(21*29)mod(32) 1 1/31=0.3225

ALGORITMOS CONGRUENCIALES:

c) Algoritmo aditivo:

Este algoritmo requiere una secuencia previa de n números enteros x1,x2,x3,x4…xn para generar una nueva secuencia de numero enteros que empiecen en xn+1,xn+2… su ecuación recursiva es: Xi+1 = (Xi-1 + Xi-n ) mod (m) i=n+1,n+2,n+3,…,N.

Para convertir los números aleatorios generados, a números pseudo-aleatorios debemos realizar esta operación:

ri= Xim−1

CARACTERISTICAS

EJEMPLO

Generar 4 números pseudo-aleatorios entre cero y uno a partir de la siguiente frecuencia de números enteros:65,89,98,03,69; m=100.

Sean x1 =65,x2=89,x3=98,x4=03,x5=69para generar r1,r2,r3,r4,r5,r6 y r7 antes es necesario generar x6,x7,x8,x9,x10.

X6=(x5+x1)mod(100) (69+65)mod 100 = 34 ------> r1=33/100-1 r1=0.3434X7=(x6+x2)mod(100) (34+89)mod 100 = 23 ------> r1=23/100-1 r1=0.2323X8=(x7+x3)mod(100) (23+98)mod 100 = 21 ------> r1=21/100-1 r1=0.2121X9=(x8+x4)mod(100) (21+03)mod 100 = 24 ------> r1=24/100-1 r1=0.2424

X10=(x9+x5)mod(100) (24+69)mod 100 = 93 ------> r1=93/100-1 r1=0.9393

ALGORITMOS CONGRUENCIALES:No lineal

a) Algoritmo cuadrático:

Este algoritmo requiere una secuencia previa de n números enteros x1,x2,x3,x4…xn para generar una nueva secuencia de numero enteros que empiecen en xn+1,xn+2… su ecuación recursiva es:Xi+1 = (aXi

2 + bxi + c) mod (m) i=0,1,2,3,4…n

De acuerdo con L’ecuyer, las condiciones que deben cumplir los parámetros m, a, b y c para alcanzar un nivel máximo de N =m son:

M=2g

a=debe ser número impar o par.c=número imparg=entero.

CARACTERISTICAS Y CONDICIONES:

EJEMPLO

Generar 5 números a partir de los siguientes parámetros:X0=13 m=8 a=26 b=27 c=27 Xi+1 = (aXi

2 + bxi + c) mod (m)

X1=[26*132 +27*13+27]mod(8) = 4X1=[26*42 +27*4+27]mod(8) = 7X1=[26*72 +27*7+27]mod(8) = 2X1=[26*22 +27*2+27]mod(8) = 1X1=[26*12 +27*1+27]mod(8) = 0

ALGORITMOS CONGRUENCIALES:No lineal

b) Algoritmo Blum Blum y Shub:

Creado a mediados de la década de 1980 por Lenore Blum ,Manuel Blum y Michael Shub . Es un algoritmo basado en congruencias cuadráticas que permite generar una secuencia

de números pseudo-aleatorios… su ecuación recursiva es:Xi = (Xi-1 )2 mod pq i=0,1,2,3,4…n

Consideraciones para generar una secuencia optima y larga:P y q son 2 numeros primos muy grande Tales que p =3mod4 y q=3mod4; esto permite asegurar que cada residuo posee una raíz cuadrada

CARACTERISTICAS Y CONDICIONES:

EJEMPLO

Generar 5 números a partir de los siguientes parámetros:X0=317 p=199 q=151 Xi = (Xi-1 )2 mod pq i=0,1,2,3,4…n

X1=(317)2 mod (199)(151)10342X2=(10342)2 mod (199)(151)12573X3=(12573)2 mod (199)(151)22589X4=(22589)2 mod (199)(151)852X5=(852)2 mod (199)(151)4728