Generador congruencial
Generador congruente lineal excel
Contenidos
Los generadores lineales congruentes (LCG) se utilizan habitualmente para generar pseudoaleatoriedad; la función rand() de muchos lenguajes de programación, por ejemplo, se implementa utilizando un LCG. Un LCG se define mediante la ecuación Ln ≡ (a ⋅ Ln-1 + c) mod m, donde los valores de m (el módulo, un entero positivo), a (el multiplicador, un entero positivo menor que m) y c (el incremento, ya sea 0 o un entero positivo menor que m) son elegidos por el diseñador del LCG. L0 (el valor “semilla”, 0 o un entero positivo menor que m) se utiliza para inicializar el LCG; la función srand() puede utilizarse en muchos lenguajes de programación para establecer el valor semilla utilizado por el LCG de la función rand().
El periodo de un LCG define la previsibilidad de su salida: en un escenario ideal, el LCG producirá m salidas consecutivas en las que cada uno de los enteros entre 0 y m-1 se emite una vez (es decir, un periodo completo). Hay que tener cuidado de elegir valores de m, a y c que maximicen el periodo del LCG; de lo contrario, el LCG produce los enteros entre 0 y m-1 de forma no uniforme, lo que proporciona una pseudoaleatoriedad de baja calidad (ya que un atacante puede predecir de forma fiable los resultados que se produjeron justo antes o justo después de un resultado concreto).
¿Cuál es la fórmula del generador congruente?
Un LCG se define mediante la ecuación Ln ≡ (a ⋅ Ln-1 + c) mod m, donde los valores de m (el módulo, un entero positivo), a (el multiplicador, un entero positivo menor que m) y c (el incremento, 0 o un entero positivo menor que m) los elige el diseñador del LCG.
¿Cuáles son las ventajas del generador congruencial lineal?
El método congruencial lineal tiene la ventaja de ser muy rápido, ya que sólo requiere unas pocas operaciones por llamada. Tiene el inconveniente de que no está libre de correlación secuencial en llamadas sucesivas.
Generador congruente lineal java
Un generador lineal congruencial combinado (CLCG) es un algoritmo generador de números pseudoaleatorios basado en la combinación de dos o más generadores lineales congruenciales (LCG). Un LCG tradicional tiene un periodo que es inadecuado para la simulación de sistemas complejos[1] Combinando dos o más LCGs, se pueden crear números aleatorios con un periodo más largo y mejores propiedades estadísticas[1].
Sea Xi,1, Xi,2, …, Xi,k salidas de k LCGs. Si Wi,j se define como Xi,j – 1, entonces Wi,j tendrá una distribución aproximadamente uniforme de 0 a mj – 1.[2] El coeficiente “(-1)j-1” realiza implícitamente la resta de uno de Xi,j.[1].
El CLCG proporciona una forma eficiente de calcular números pseudoaleatorios. El algoritmo LCG es de bajo coste computacional[3] Los resultados de múltiples algoritmos LCG se combinan a través del algoritmo CLCG para crear números pseudoaleatorios con un periodo más largo que el que se puede conseguir con el método LCG por sí mismo[3].
El periodo de un CLCG es el mínimo común múltiplo de los periodos 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 manera que 2 es el máximo común divisor de cada par, esto dará lugar a un período de:[1].
Fórmula generatriz congruente lineal
Dos LCG modulo-9 muestran cómo diferentes parámetros conducen a diferentes longitudes de ciclo. Cada fila muestra la evolución del estado hasta que se repite. La fila superior muestra un generador con m = 9, a = 2, c = 0 y una semilla de 1, que produce un ciclo de longitud 6. La segunda fila es el mismo generador con una semilla de 3, que produce un ciclo de longitud 2. Utilizando a = 4 y c = 1 (fila inferior) se obtiene una longitud de ciclo de 9 con cualquier semilla en [0, 8].
Un generador lineal congruente (LCG) es un algoritmo que produce una secuencia de números pseudoaleatorios calculados con una ecuación lineal discontinua a trozos. Este método representa uno de los algoritmos generadores de números pseudoaleatorios más antiguos y conocidos. La teoría que los sustenta es relativamente fácil de entender, y son fáciles de implementar y rápidos, especialmente en hardware informático que pueda proporcionar aritmética modular mediante truncamiento de bits de almacenamiento.
son constantes enteras que especifican el generador. Si c = 0, el generador suele denominarse generador congruente multiplicativo (MCG) o RNG de Lehmer. Si c ≠ 0, el método se denomina generador congruencial mixto[1]: 4-
Generador congruente lineal en c
Tal generador es fácil de implementar, y pasa las siguientes pruebas estadísticas: Postulados de aleatoriedad de Golomb, prueba de frecuencia, prueba de serie, prueba de póquer, prueba de carreras, prueba de autocorrelación y prueba estadística universal de Maurer. Por tanto, puede considerarse un buen candidato para generar secuencias pseudoaleatorias fuertes. Sin embargo, tiene un inconveniente importante: la secuencia es predecible: dado un trozo de la secuencia, es fácil reconstruir todo el resto, aunque…
. https://doi.org/10.1007/0-387-23483-7_231Download citationCompartir esta entradaCualquier persona con la que compartas el siguiente enlace podrá leer este contenido:Get shareable linkSorry, a shareable link is not currently available for this article.Copy to clipboard