Algoritmo congruencial multiplicativo

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

G debe ser enterición) de m/4 o de 

$2^{g-2}$

Algoritmo Lineal

Algoritmo Lineal

El algoritmo congruencial lineal genera una secuencia de números enteros por medio de la siguiente ecuación recursiva:


X1+1 = (aX0 + b) mod(m)


donde X0 es la semilla, a es la constante multiplicativa, b es una constante aditiva y m es el módulo; X0 > 0, a > 0, b > 0 y m > 0 deben ser números enteros. La operación "mod m" significa multiplicar Xi por a, sumar b y dividir el resultado entre m para obtener el residuo Xi+1. Es importante señalar que la ecuación recursiva del algoritmo congruancial lineal genera una secuencia de números S = {0,1,2,3,...,m-1}, y que para obtener números pseudo aleatorios en el intervalo (0,1) se requiere la siguiente ecuación:


ri = Xi/(m-1)

Este algoritmo congruencial fue propuesto por D.H,Lehmer en 1951.Segun Law y Kelton, este algortimo ha sido el mas usado. El algoritmo congruenca lineal genera una secuencia de numeros enteros por medio de la siguiente ecuacion recursiva:

X_i+1=(aX_i+C)mod(m)      i=0,1,2,3,...,n.

donde X0 es la semilla, a es la constante muliplicativa c, es una constante aditiva y m es el modulo;Xo>,a>0,c>0, m>0 deben ser numeros enteros.La operacion "mod m"significa multiplicar X, por a, sumar c y dividir el resultado entre m paa obtener el residuo X1+i. .Es importante señalar que la ecuacion recursiva del algoritmo congruencial lineal genera una secuencia de numeros enteros s={1,2,,2,..,m-1), y que para obtner numeros pseudo aleatorios en el intervalo(0,1) se requiere la siguiente ecuacion:

ri=Xi/m-1    i-1,2,3...n

Véase en el archivo excel:https://app.box.com/s/zuqxn58usn0t6w0s6cv7r1mbo2ug6tps

Multiplicador Constante

Algoritmo de multiplicador constante

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.

Ejemplo en Excel:

https://app.box.com/s/3dya2dietgpxmyawjidoedubbyhmeq4o

Productos Medios

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.

Ejemplo en Excel:

https://app.box.com/s/360xa8khg4u76kivh62jmigxdjxcmmje