Métodos de congruencias para generadores pseudoaleatorios: aditivo, multiplicativo y mixto
Resumen
El documento explica el método de las congruencias para generar números pseudoaleatorios a partir de una relación fundamental de recurrencia módulo m. Describe tres variantes: el método aditivo, el multiplicativo y el mixto, junto con sus relaciones de recurrencia. También recoge las condiciones y recomendaciones para elegir los parámetros que mejoran el período y las propiedades estadísticas de la sucesión.
Puntos clave
- La relación fundamental es Vi+1 = (a Vi + c Vi-k) mod m, y los términos forman una sucesión módulo m.
- El método aditivo se obtiene con a = 1 y c = 1, y requiere k+1 valores iniciales enteros y positivos.
- El método aditivo es el único de los métodos de congruencias que produce períodos mayores que m.
- El método multiplicativo se obtiene con c = 0 y puede fijarse a y la semilla V0 para alcanzar un período máximo.
- En el método multiplicativo decimal, a = 200·t·p, donde p toma valores como 3, 11, 13, 19 o 21, entre otros.
- El método mixto se obtiene con Vi-k = ... = Vi-1 = 1 y, con una buena elección de a y c, el período puede cubrir los m números distintos.
Método de las Congruencias para Generadores Pseudoaleatorios
Relación fundamental de congruencias
La relación fundamental empleada es:
Vi+1 = (a Vi + c Vi-k) mod m, donde Vi, Vi-k, a, c, k y m son enteros no negativos y arbitrarios que cumplen las siguientes condiciones:
- Vi > 0
- a > 0
- c > 0
- m > Vi
- m > a
- m > 0
En lenguaje corriente, la ecuación anterior significa que el i-ésimo número de la sucesión (Vi+1) es igual al residuo que queda al dividir (a Vi + c Vi-k) por m. Los términos obtenidos por esta relación forman una sucesión módulo m (Vi < m para todo Vi de la sucesión).
Método Aditivo de Congruencias
Relación de recurrencia:
Vi+1 = (Vi + Vi-k) mod m
Este método presupone k+1 valores enteros y positivos iniciales. Se obtiene de la relación fundamental haciendo a = 1 y c = 1.
Propiedades y recomendaciones:
- Las propiedades estadísticas de la sucesión mejoran a medida que k se incrementa.
- Es el único método de congruencias que produce períodos mayores que m.
- Conviene asignar a los parámetros iniciales números primos, y con tantos dígitos como pueda soportar el sistema operativo de la computadora.
Método Multiplicativo de Congruencias
Relación de recurrencia:
Vi+1 = (a Vi) mod m
Se obtiene de la relación fundamental haciendo c = 0.
Características y condiciones:
- Es posible imponer condiciones al parámetro a y al valor inicial V0 (semilla) para asegurar un período máximo para las sucesiones.
- Si se trabaja en sistema decimal, los valores de los parámetros deben seleccionarse según los siguientes criterios:
- a) El valor de Vi debe ser cualquier entero impar no divisible por 2 ni por 5 y debe ser relativamente primo con m.
- b) Obtener el valor de a de acuerdo a la siguiente identidad: a = 200·t·p, donde t es cualquier entero y p es cualquiera de los siguientes valores: 3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61, 67, 69, 77, 83, 91.
Método Mixto de Congruencias
Relación de recurrencia:
Vi+1 = (a Vi + c) mod m
Se obtiene haciendo Vi-k = Vi-k+1 = ... = Vi-1 = 1.
Con la selección adecuada de los parámetros a y c, el período puede cubrir todo el conjunto de m números diferentes.
Condiciones recomendadas para los parámetros:
- a) El valor de a debe ser entero impar y no debe ser divisible por 3 ni por 5. Usualmente se selecciona a como 2k + 1 en sistema binario y 10k + 1 en el sistema decimal. En ambos casos k ≥ 2.
- b) El valor de c debe ser un entero impar y relativamente primo con m.
Notas finales
Cada uno de estos métodos tiene aplicaciones y limitaciones según el contexto de generación de números pseudoaleatorios. La correcta elección de los parámetros y las condiciones iniciales es clave para lograr buenos periodos y propiedades estadísticas en la sucesión generada.
Descargar
PDF Word HTMLPreguntas frecuentes
¿En qué se diferencia el método aditivo del multiplicativo?
El método aditivo usa la recurrencia Vi+1 = (Vi + Vi-k) mod m, obtenida con a = 1 y c = 1. El multiplicativo usa Vi+1 = (a Vi) mod m, obtenida con c = 0.
¿Qué condiciones debe cumplir el parámetro a en el método mixto?
El valor de a debe ser un entero impar que no sea divisible por 3 ni por 5. Usualmente se elige como 2k + 1 en binario o 10k + 1 en decimal, con k ≥ 2.
Ponte a prueba
Tarjetas de repaso
Pulsa una tarjeta para ver la respuesta.
Test
Preguntas generadas con IA a partir del documento: comprueba las respuestas con el texto.