El algoritmo congruencial multiplicativo se utiliza para generar números pseudo aleatorios. Veamos a continuación una explicación de en qué consiste así como su implementación en Java.
¿Cómo se generan los números pseudo aleatorios? De seguro al utilizar alguna función para generar números pseudo aleatorios en cualquier lenguaje de programación nos preguntamos cómo se generan y si podemos confiar en su “aleatoriedad”. (En un artículo de Bravo y Sanchez se menciona que la función RND del lenguaje QBasic implementaba un algoritmo congruencial lineal)
En la disciplina de la Simulación se estudia este aspecto tan importante de los sistemas computacionales.
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^gA = 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
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
Por lo que se puede observar, se logran los 16 números, a partir del número 17 se comienzan a repetir.
Bibliografía
- García, García y Cárdenas (2006). Simulación y análisis de sistemas con Promodel. Ed. Pearson.
- Sánchez-Pajares y Bravo (2002). Una función random poco aleatoria. Revista española de física, 16(2), 60-62. Disponible en: [https://www.eweb.unex.es/eweb/fisteor/santos/PUBLICATIONS/a02YusSan-PajREFv16n2p60.pdf]
Tu comentario
opiniones