Un combinado lineal generador de congruencia ( CLCG ) es una pseudo-aleatorio generador de números algoritmo basado en la combinación de dos o más generadores de congruencia lineal (LCG). Una LCG tradicional tiene un período que es inadecuado para la simulación de sistemas complejos. [1] Al combinar dos o más LCG, se pueden crear números aleatorios con un período más largo y mejores propiedades estadísticas. [1] El algoritmo se define como: [2]
dónde:
- es el " módulo " del primer LCG
- es la i- ésima entrada de la j- ésima LCG
- es el i- ésimo entero aleatorio generado
con:
dónde es un número aleatorio distribuido uniformemente entre 0 y 1.
Derivación
Si W i , 1 , W i , 2 , ..., W i , k son variables aleatorias independientes, discretas, y una de ellas se distribuye uniformemente de 0 am 1 - 2, entonces Z i se distribuye uniformemente entre 0 y m 1 - 2, donde: [2]
Sean X i , 1 , X i , 2 , ..., X i , k salidas de k LCG. Si W i , j se define como X i , j - 1, entonces W i , j se distribuirá aproximadamente uniformemente de 0 am j - 1. [2] El coeficiente "(−1) j −1 " implícitamente realiza el resta de uno de X i , j . [1]
Propiedades
El CLCG proporciona una forma eficaz de calcular números pseudoaleatorios. El algoritmo LCG es de uso económico desde el punto de vista computacional. [3] Los resultados de múltiples algoritmos LCG se combinan a través del algoritmo CLCG para crear números pseudoaleatorios con un período más largo que el que se puede lograr con el método LCG por sí mismo. [3]
El período de un CLCG es el mínimo común múltiplo de los períodos de los generadores individuales, que son uno menos que los módulos. Dado que todos los módulos son primos impares, los períodos son pares y, por lo tanto, comparten al menos un divisor común de 2, pero si los módulos se eligen de modo que 2 sea el máximo divisor común de cada par, esto dará como resultado un período de: [ 1]
Ejemplo
El siguiente es un algoritmo de ejemplo diseñado para su uso en computadoras de 32 bits: [2]
Los LCG se utilizan con las siguientes propiedades:
El algoritmo CLCG se configura de la siguiente manera:
1. La semilla de la primera LCG, , debe seleccionarse en el rango de [1, 2147483562].
- La semilla de la segunda LCG, , debe seleccionarse en el rango de [1, 2147483398].
- Colocar:
2. Los dos LCG se evalúan de la siguiente manera:
3. La ecuación CLCG se resuelve como se muestra a continuación:
4. Calcule el número aleatorio:
5. Incremente el contador ( i = i + 1), luego regrese al paso 2 y repita.
El período máximo de las dos LCG utilizadas se calcula mediante la fórmula :. [1]
Esto equivale a 2,1 × 10 9 para las dos LCG utilizadas.
Este CLCG que se muestra en este ejemplo tiene un período máximo de:
Esto representa una tremenda mejora durante el período de las LCG individuales. Puede verse que el método combinado aumenta el período en 9 órdenes de magnitud.
Sorprendentemente, el período de este CLCG puede no ser suficiente para todas las aplicaciones. [1] Se han utilizado otros algoritmos que utilizan el método CLCG para crear generadores de números pseudoaleatorios con períodos de hasta 3 × 10 57 . [4] [5] [6]
Ver también
- Generador de congruencia lineal
- Wichmann – Hill , una LCG combinada específica propuesta en 1982
Referencias
- ^ a b c d e f Banks, Jerry; Carson, John S .; Nelson, Barry L .; Nicol, David M. (2010). Simulación de sistemas de eventos discretos (5ª ed.). Prentice Hall. § 7.3.2. ISBN 0-13-606212-1.
- ^ a b c d L'Ecuyer, Pierre (1988). "Generadores de números aleatorios combinados eficientes y portátiles" (PDF) . Comunicaciones de la ACM . 31 (6): 742–749, 774. CiteSeerX 10.1.1.72.88 . doi : 10.1145 / 62959.62969 .
- ^ a b Pandey, Niraj (6 de agosto de 2008). Implementación de la función Leap Ahead para generadores de Fibonacci lineales congruentales y retardados (PDF) (tesis de maestría). Universidad Estatal de Florida. § 2.2. Archivado desde el original (PDF) el 12 de julio de 2011 . Consultado el 13 de abril de 2012 .
- ^ L'Ecuyer, Pierre (septiembre-octubre de 1996). "Generadores de números recursivos múltiples combinados" . Investigación operativa . 44 (5): 816–822. doi : 10.1287 / opre.44.5.816 .
- ^ L'Ecuyer, Pierre (enero-febrero de 1999). "Buenos parámetros e implementaciones para generadores de números aleatorios recursivos múltiples combinados" . Investigación operativa . 47 (1): 159-164. CiteSeerX 10.1.1.48.1341 . doi : 10.1287 / opre.47.1.159 .
- ^ L'Ecuyer, Pierre; R. Simard; EJ Chen; WD Kelton (noviembre-diciembre de 2002). "Un paquete de números randon orientado a objetos con muchos flujos largos y subflujos" (PDF) . Investigación operativa . 50 (6): 1073–1075. CiteSeerX 10.1.1.25.22 . doi : 10.1287 / opre.50.6.1073.358 .
enlaces externos
- Una descripción general del uso y las pruebas de generadores de números pseudoaleatorios