ALGORITMO CONGRUENCIAL MULTIPLICATIVO

https://app.box.com/s/u1as1bdkunnknqahgfxjg3yzpp3lwaf4

Algoritmo Congruencial Multiplicativo

Un algoritmo que se utiliza para generar números pseudo aleatorios, es el algoritmo congruencia multiplicativo. Tiene como base al algoritmo congruencia lineal pero conlleva una operación menos.

La operación principal es la siguiente:

$X_{i+1} = (aX_{i}) mod (m)$

Es decir, se toma una semilla a la que llamaremos $X_{0}$. Se multiplica por un número a y al resultado de la multiplicación se divide por m recuperando solo el residuo o módulo de la división. Este valor será X1, y así sucesivamente.

Esta operación nos da un valor entero. Si deseamos un número pseudo aleatorio en el intervalo (0,1), debemos realizar la siguiente operación sobre el número anteriormente obtenido.

$R_{i} = X_{i} / (m-1)$

Es decir, al número que produjo la primera operación, se le divide entre m-1. Nos dará un valor entre 0 y 1.

Para mejorar la eficiencia del algoritmo se deben seguir ciertas condiciones para los valores $a, m, X_{0}$. (Banks, Carson, Nelson y Nicol, citados por García, García y Cárdenas (2006).

Condiciones

$M = 2^g$

$A = 3+8k$ o bien $a = 5+8k$

K = 0,1,2,3,…

$X_{0}$ debe ser impar

algoritmo lineal

https://app.box.com/s/os2mcy0pczgomsj24kcqe57b46crpgei



que es algoritmo lienal?

Algoritmo 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: 

( )mod( ) Xi+1 = a Xi + c 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: 

−1 = m X r i i 

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 g 2 , 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: g N = m = 2 . 

productos medios

https://app.box.com/s/04m5nam2vy0r0n5k9tmwdkhwg0o2qdkv

Algoritmo de productos medios

Este algoritmo es similar al anterior, la diferencia entre los dos es que este algoritmo requiere de dos semillas; ambas con D dígitos; además de elevarlas al cuadrado, las semillas se multiplican y del producto resultante se seleccionan los D dígitos del centro, los cuales formaran el primer número de D dígitos. Después se elimina una semilla y la otra se multiplica por el primer número de D dígitos, para luego seleccionar del producto los D dígitos que conformaran un segundo número ri. Entonces se elimina la segunda semilla, y se multiplica el primer número de los D dígitos por el segundo número de los D dígitos; del producto se obtiene el tercer número de ri. Siempre se ira eliminando el número más antiguo y el procedimiento se repetirá hasta generar los n números pseudo aleatorios.

Pasos para generar números con el algoritmo de producto medios:

1.- Seleccionar una semilla (X0) con D dígitos (D>3).

2.- Seleccionar una semilla (X0) con D dígitos (D>3).

3.- Sea Y0 = X0 * X1; sea X2 = los D dígitos del centro, y sea ri = 0. D dígitos del centro.

4.- Sea Yi = X1 * Xi+1; sea Xi+2 = los D dígitos del centro, y sea ri+1 = 0. D dígitos del centro para toda i= 1, 2, 3,…, n.

5.- Repetir el paso 4 hasta obtener los n números ri deseados.

Si no es posible obtener los D dígitos del centro del número Yi, agregue ceros a la izquierda del numero Yi.

multiplicador constante

https://app.box.com/s/h0bkp8bbaveaofmrkqevba3u62k98rzg



Algoritmo de multiplicador constante

Este algoritmo no congruencial es similar al algoritmo de productos medios. 

Los siguientes son los pasos necesarios para generar números pseudo aleatorios con el algoritmo de multiplicador constante. 

1. Selecciona una semilla ( ) X0 con D dígitos (D > 3). 

2. Seleccionar una constante (a) con D dígitos (D > 3). 

3. Sea Y0 = a * X0 ; sea X1 = los D dígitos del centro y sea r1 = 0.D dígitos del centro. 

4. Sea Yi = a * Xi ; sea Xi+1 = los D dígitos del centro y sea ri+1 = 0.D dígitos del centro para toda i = 1, 2, 3,...,n . 

5. Repetir el paso 4 hasta obtener los n números ir deseados.