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 entero
Si se siguen estas condiciones se puede lograr que el algoritmo tenga un período de vida (iteraciones sin encontrar repetición) de m/4 o de 2^{g-2}
Veamos su implementación en el lenguaje java.

Algoritmo Congruencial Multiplicativo en Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Scanner entrada = new Scanner(System.in); 
int semilla, cmultiplicativa, caditiva, modulo; 
int i, numero; 
double numero2; 
System.out.print("Escriba una semilla: ");
semilla = entrada.nextInt();
System.out.print("Escriba una constante multiplicativa: ");
cmultiplicativa= entrada.nextInt();
System.out.print("Escriba el módulo: ");
modulo = entrada.nextInt();
for (i=1; i<=20; i++){
   numero = (cmultiplicativa*semilla) % modulo;   
   numero2 = (double)numero / (double)(modulo-1);
   System.out.printf("%d. %d (%.4f)\n", i ,numero ,numero2 );
   semilla = numero; 
}

Explicación

  • Scanner entrada = new Scanner(System.in);  Para recibir datos del teclado del usuario
  • int semilla, cmultiplicativa, caditiva, modulo;  Variables que guardan los valores necesarios: semilla, constante multiplicativa, constante aditiva, valor para dividir y obtener el módulo o residuo.
  • int i, numero;  i se usa en el ciclo for, y número recibirá el resultado del siguiente número pseudo aleatorio.
  • double numero2;  Valor que tendrá el número pseudo aleatorio en el rango 0 a 1.
Las siguientes líneas solicitan los datos al usuario.
  • System.out.print(“Escriba una semilla: “);
  • semilla = entrada.nextInt();
  • System.out.print(“Escriba una constante multiplicativa: “);
  • cmultiplicativa= entrada.nextInt();
  • System.out.print(“Escriba el módulo: “);
  • modulo = entrada.nextInt();
Con un for generamos 20 números:
  • for (i=1; i<=20; i++){
  • numero = (cmultiplicativa*semilla) % modulo;  Operación de la fórmula
  • numero2 = (double)numero / (double)(modulo-1);  Operación para obtener el valor en el rango de 0 a 1
  • System.out.printf(“%d. %d (%.4f)\n”, i ,numero ,numero2 ); Impresión del resultado
  • semilla = numero;  Se utilizará el número entero obtenido como semilla de la siguiente operación.

Prueba

Se desean obtener 16 números pseudo aleatorios usando el algoritmo congruencia multiplicativo:
Para obtener 16 se necesita que m= 64 pues el período de vida máximo = m/4 o 64/4=16. Es decir, g=6 pues 2^6 = 64, y el periodo de vida es de 2^{6-2} = 2^4 = 16
X_0 debe ser impar, por lo que seleccionamos 15
K = 4 por lo que a= 3+8(4) = 35
https://app.box.com/file/636668822413

Comentarios

Publicar un comentario