Generador lineal congruente

Dos modulo-9 LCGs muestran cómo diferentes parámetros conducen a diferentes longitudes de ciclo. Cada fila muestra el estado evolucionando 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. Uso a= 4 y c= 1 (la fila inferior) da 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 por partes. El método representa uno de los algoritmos generadores de números pseudoaleatorios más antiguos y conocidos. La teoría detrás de ellos es relativamente fácil de entender, y se implementan con facilidad y rapidez, especialmente en hardware de computadora que puede proporcionar aritmética modular mediante el truncamiento de bits de almacenamiento.

El generador está definido por la relación de recurrencia:

Xn+1=()aXn+c)modm{displaystyle X_{n+1}=left(aX_{n}+cright){bmod {m}}

Donde X{displaystyle X} es la secuencia de valores pseudo-aleatorios, y

<math alttext="{displaystyle m,,0m,0.m{displaystyle m,,0}<img alt="m,,0 - el "modulo"

<math alttext="{displaystyle a,,0<aa,0.a.m{displaystyle a,,0cantada<img alt="a,,0<a - el "multiplier"

<math alttext="{displaystyle c,,0leq cc,0≤ ≤ c.m{displaystyle c,,0leq ccanta}<img alt="c,,0leq c - el "incremento"

<math alttext="{displaystyle X_{0},,0leq X_{0}X0,0≤ ≤ X0.m{displaystyle X_{0},,0leq X.<img alt="X_{0},,0leq X_{0} — la "semilla" o "valor inicial"

son constantes enteras que especifican el generador. Si c = 0, el generador a menudo se denomina generador congruencial multiplicativo (MCG) o Lehmer RNG. Si c ≠ 0, el método se denomina generador congruencial mixto.

Cuando c ≠ 0, un matemático llamaría a la recurrencia una transformación afín, no lineal, pero el nombre inapropiado está bien establecido en la informática.

Historia

El generador de Lehmer se publicó en 1951 y el generador de congruencia lineal se publicó en 1958 por W. E. Thomson y A. Rotenberg.

Duración del período

Un beneficio de los LCG es que una elección adecuada de parámetros da como resultado un período conocido y largo. Aunque no es el único criterio, un período demasiado corto es un defecto fatal en un generador de números pseudoaleatorios.

Si bien los LCG son capaces de producir números pseudoaleatorios que pueden pasar pruebas formales de aleatoriedad, la calidad de la salida es extremadamente sensible a la elección de los parámetros m y a. Por ejemplo, a = 1 y c = 1 produce un contador de módulo-m simple, que tiene un período largo, pero obviamente no es aleatorio.

Históricamente, las malas elecciones para a han llevado a implementaciones ineficaces de LCG. Un ejemplo particularmente ilustrativo de esto es RANDU, que se usó ampliamente a principios de la década de 1970 y condujo a muchos resultados que actualmente se cuestionan debido al uso de este pobre LCG.

Hay tres familias comunes de elección de parámetros:

M primo, c = 0

Esta es la construcción RNG original de Lehmer. El período es m−1 si el multiplicador a se elige como un elemento primitivo de los enteros módulo m. El estado inicial debe elegirse entre 1 y m−1.

Una desventaja de un módulo primo es que la reducción modular requiere un producto de doble ancho y un paso de reducción explícito. A menudo se usa un número primo justo menor que una potencia de 2 (los números primos de Mersenne 2³¹−1 y 2⁶¹−1 son populares), de modo que el módulo de reducción m = 2^e − d se puede calcular como (ax mod 2 ^e) + d ⌊hacha/2^e⌋. Esto debe ir seguido de una resta condicional de m si el resultado es demasiado grande, pero el número de restas está limitado a ad/m, que se puede limitar fácilmente a uno si d es pequeño.

Si un producto de doble ancho no está disponible y el multiplicador se elige cuidadosamente, se puede usar el método de Schrage. Para hacer esto, factorice m = qa+r, es decir, q = ⌊m/a⌋ y r = m mod a. Luego calcule ax mod m = a(x mod q ) − r⌊x/q⌋. Dado que x mod q < q ≤ m/a, el primer término es estrictamente menor que am/a = m. Si se elige a de modo que r ≤ q (y por lo tanto r/q ≤ 1), entonces el segundo término también es menor que m: r⌊x /q⌋ ≤ rx/q = x(r/q) ≤ x < m. Por lo tanto, ambos productos se pueden calcular con un producto de ancho simple, y la diferencia entre ellos se encuentra en el rango [1−m, m−1], por lo que puede ser reducido a [0, m−1] con una sola adición condicional.

Una segunda desventaja es que es complicado convertir el valor 1 ≤ x < m a bits aleatorios uniformes. Si se usa un número primo justo menor que una potencia de 2, a veces simplemente se ignoran los valores que faltan.

M una potencia de 2, c = 0

Elegir m como una potencia de 2, normalmente m = 2³² o m = 2 ⁶⁴, produce un LCG particularmente eficiente, porque permite calcular la operación del módulo simplemente truncando la representación binaria. De hecho, los bits más significativos normalmente no se calculan en absoluto. Hay, sin embargo, desventajas.

Este formulario tiene un período máximo m/4, alcanzado si a ≡ 3 o a ≡ 5 (mod 8). El estado inicial X₀ debe ser impar, y los tres bits bajos de X alternan entre dos estados y no son útiles. Se puede demostrar que esta forma es equivalente a un generador con un módulo de un cuarto del tamaño y c ≠ 0.

Un problema más serio con el uso de un módulo de potencia de dos es que los bits bajos tienen un período más corto que los bits altos. El bit de menor orden de X nunca cambia (X siempre es impar) y los siguientes dos bits alternan entre dos estados. (Si a ≡ 5 (mod 8), el bit 1 nunca cambia y el bit 2 se alterna. Si a ≡ 3 (mod 8), el bit 2 nunca cambia y el bit 1 alterna.) El bit 3 se repite con un período de 4, el bit 4 tiene un período de 8, y así sucesivamente. Solo la parte más significativa de X alcanza el período completo.

C ≠ 0

Cuando c ≠ 0, los parámetros elegidos correctamente permiten un período igual a m, para todos los valores semilla. Esto ocurrirá si y sólo si:

1. m{displaystyle m} y c{displaystyle c} son relativamente primos,
2. a− − 1{displaystyle a-1} es divisible por todos los factores principales m{displaystyle m},
3. a− − 1{displaystyle a-1} es divisible por 4 si m{displaystyle m} es divisible por 4.

Estos tres requisitos se conocen como el Teorema de Hull-Dobell.

Esta forma se puede usar con cualquier m, pero solo funciona bien para m con muchos factores primos repetidos, como una potencia de 2; usar el tamaño de palabra de una computadora es la opción más común. Si m fuera un número entero sin cuadrados, esto solo permitiría a ≡ 1 (mod m), lo que hace un PRNG muy pobre; una selección de posibles multiplicadores de período completo solo está disponible cuando m tiene factores primos repetidos.

Aunque el teorema de Hull-Dobell proporciona un período máximo, no es suficiente para garantizar un buen generador. Por ejemplo, es deseable que a − 1 no sea más divisible por factores primos de m de lo necesario. Por lo tanto, si m es una potencia de 2, entonces a − 1 debería ser divisible por 4 pero no por 8, es decir, a ≡ 5 (mod 8).

De hecho, la mayoría de los multiplicadores producen una secuencia que falla en una u otra prueba de no aleatoriedad, y encontrar un multiplicador que satisfaga todos los criterios aplicables es todo un desafío. La prueba espectral es una de las pruebas más importantes.

Tenga en cuenta que un módulo de potencia de 2 comparte el problema descrito anteriormente para c = 0: los bits bajos k forman un generador con módulo 2 ^k y así repetir con un período de 2^k; solo el bit más significativo alcanza el período completo. Si se desea un número pseudoaleatorio menor que r, ⌊rX/m</i ⌋ es un resultado de mucha mayor calidad que X mod r. Desafortunadamente, la mayoría de los lenguajes de programación hacen que este último sea mucho más fácil de escribir (X % r), por lo que es la forma más utilizada.

El generador no es sensible a la elección de c, siempre que sea relativamente primo al módulo (por ejemplo, si m es una potencia de 2, entonces c debe ser impar), por lo que comúnmente se elige el valor c=1.

La serie producida por otras opciones de c se puede escribir como una función simple de la serie cuando c=1. Específicamente, si Y es la serie prototípica definida por Y₀ = 0 y Y _n+1 = aY_n+1 mod m, luego una serie general X_n+1 = aX_n+c mod m se puede escribir como una función afín de Y:

Xn=()X0()a− − 1)+c)Yn+X0=()X1− − X0)Yn+X0()modm).{displaystyle Y... {m}}

Más generalmente, dos series cualesquiera X y Z con el mismo multiplicador y módulo están relacionadas por

Xn− − X0X1− − X0=Yn=an− − 1a− − 1=Zn− − Z0Z1− − Z0()modm).{displaystyle {X_{n}-X_{0} over X_{1}-X_{0}=Y_{n}={a^{n}-1 over a-1}={Z_{n}-Z_{0} over Z_{1}-Z_{0}{pmod {m}}

Parámetros de uso común

La siguiente tabla enumera los parámetros de los LCG de uso común, incluidas las funciones rand() integradas en las bibliotecas de tiempo de ejecución de varios compiladores. Esta tabla es para mostrar popularidad, no ejemplos para emular; muchos de estos parámetros son malos. Hay disponibles tablas de buenos parámetros.

Fuente	modulus m	multiplicador a	aumento c	bits de producción de semilla en rand() o Random(L)
ZX81	216 + 1	75	74
Recetas numéricas de la lista de "ganadores rápidos y sucios", Capítulo 7.1, Eq. 7.1.6 parámetros de Knuth y H. W. Lewis	232	1664525	1013904223
Borland C/C++	232	22695477	1	bits 30..16 in rand(), 30.0 en Irand()
glibc (used by GCC)	231	1103515245	12345	bits 30.0.
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM Visual Edad C/C++ C90, C99, C11: Sugerencia en la ISO/IEC 9899, C17	231	1103515245	12345	bits 30..16
Borland Delphi, Virtual Pascal	232	134775813	1	bits 63.32 de (seed × L)
Turbo Pascal	232	134775813 (808840516)	1
Microsoft Visual/Quick C/C++	232	214013 (343FD16)	2531011 (269EC316)	bits 30..16
Microsoft Visual Basic (6 y anterior)	224	1140671485 (43FD43FD16)	12820163 (C39EC316)
RtlUniform de la API nativa	231 − 1	2147483629 (7FFFED16)	2147483587 (7FFFC316)
Apple CarbonLib, C+11's minstd_rand0, MATLAB v4 legado generador mcg16807	231 − 1	16807	0	ver MINSTD
C++11's minstd_rand	231 − 1	48271	0	ver MINSTD
MMIX por Donald Knuth	264	6364136223846793005	1442695040888963407
Newlib	264	6364136223846793005	1	bits 62..32 (46..32 for 16-bit int)
Musl	264	6364136223846793005	1	bits 63..33.
VMS MTH$RANDOM, versiones antiguas de glibc	232	69069 (10DCD16)	1
Java's java.util. Random, POSIX [ln]rand48, glibc [ln]rand48[_r]	248	25214903917 (5DEECE66D16)	11	bits 47..16
random0	134456 = 2375	8121	28411	Xn134456{displaystyle {frac {X_{n}{134456}}
POSIX [jm]rand48, glibc [mj]rand48[_r]	248	25214903917 (5DEECE66D16)	11	bits 47..15
POSIX [de]rand48, glibc [de]rand48[_r]	248	25214903917 (5DEECE66D16)	11	bits 47..0
cc65	223	65793 (10101)16)	4282663 (41592716)	bits 22..8
cc65	232	16843009 (101010116)	826366247 (3141592716)	bits 31..16
cc65	232	16843009 (101010116)	3014898611 (B3B3B3B3B316)	bits 31..16, bits actuales 31..16 xor bits 14..0
Anteriormente común: RANDU	231	65539	0

Como se muestra arriba, los LCG no siempre usan todos los bits en los valores que producen. Por ejemplo, la implementación de Java opera con valores de 48 bits en cada iteración, pero devuelve solo los 32 bits más significativos. Esto se debe a que los bits de orden superior tienen períodos más largos que los bits de orden inferior (ver más abajo). Los LCG que utilizan esta técnica de truncamiento producen valores estadísticamente mejores que los que no lo hacen. Esto es especialmente notable en scripts que usan la operación mod para reducir el rango; modificar el número aleatorio mod 2 conducirá a alternar 0 y 1 sin truncamiento.

Ventajas y desventajas

Los LCG son rápidos y requieren una memoria mínima (un número de módulo-m, a menudo de 32 o 64 bits) para conservar el estado. Esto los hace valiosos para simular múltiples flujos independientes. Los LCG no están destinados y no deben usarse para aplicaciones criptográficas; use un generador de números pseudoaleatorios criptográficamente seguro para tales aplicaciones.

Hiperplanos de un generador lineal congruencial en tres dimensiones. Esta estructura es lo que mide la prueba espectral.

Aunque los LCG tienen algunas debilidades específicas, muchas de sus fallas provienen de tener un estado demasiado pequeño. El hecho de que la gente haya sido engañada durante tantos años para usarlos con módulos tan pequeños puede verse como un testimonio de la fuerza de la técnica. Un LCG con un estado lo suficientemente grande puede pasar incluso pruebas estadísticas estrictas; un LCG de módulo 2 que devuelve los 32 bits altos pasa la suite SmallCrush de TestU01, y un LCG de 96 bits pasa la suite BigCrush más estricta.

Para un ejemplo específico, se espera que un generador de números aleatorios ideal con 32 bits de salida (según el teorema de Birthday) comience a duplicar salidas anteriores después de √m ≈ 2¹⁶ resultados. Cualquier PRNG cuyo resultado sea su estado completo y no truncado no producirá duplicados hasta que transcurra su período completo, una falla estadística fácilmente detectable. Por razones relacionadas, cualquier PRNG debe tener un período mayor que el cuadrado del número de salidas requeridas. Dadas las velocidades de las computadoras modernas, esto significa un período de 2⁶⁴ para todas las aplicaciones menos las menos exigentes, y más largo para las simulaciones más exigentes.

Un defecto específico de los LCG es que, si se utilizan para elegir puntos en un espacio n-dimensional, los puntos se ubicarán, como máximo, en ⁿ√n!⋅m hiperplanos (teorema de Marsaglia, desarrollado por George Marsaglia). Esto se debe a la correlación serial entre valores sucesivos de la secuencia X_n. Los multiplicadores elegidos sin cuidado suelen tener muchos menos planos, muy espaciados, lo que puede generar problemas. La prueba espectral, que es una prueba simple de la calidad de un LCG, mide este espaciado y permite elegir un buen multiplicador.

La distancia entre planos depende tanto del módulo como del multiplicador. Un módulo lo suficientemente grande puede reducir esta distancia por debajo de la resolución de los números de doble precisión. La elección del multiplicador se vuelve menos importante cuando el módulo es grande. Todavía es necesario calcular el índice espectral y asegurarse de que el multiplicador no sea malo, pero puramente probabilísticamente es extremadamente improbable encontrar un multiplicador malo cuando el módulo es mayor que aproximadamente 2⁶⁴.

Otro defecto específico de los LCG es el período breve de los bits de orden inferior cuando se elige m como una potencia de 2. Esto se puede mitigar utilizando un módulo mayor que la salida requerida, y usando los bits más significativos del estado.

Sin embargo, para algunas aplicaciones, los LCG pueden ser una buena opción. Por ejemplo, en un sistema integrado, la cantidad de memoria disponible suele estar muy limitada. De manera similar, en un entorno como una consola de videojuegos, puede ser suficiente tomar una pequeña cantidad de bits de alto orden de un LCG. (Nunca se debe confiar en los bits de bajo orden de los LCG cuando m es una potencia de 2 para ningún grado de aleatoriedad). Los bits de bajo orden pasan por ciclos muy cortos. En particular, cualquier LCG de ciclo completo, cuando m es una potencia de 2, producirá alternativamente resultados pares e impares.

Los LCG deben evaluarse con mucho cuidado para determinar su idoneidad en aplicaciones no criptográficas donde la aleatoriedad de alta calidad es crítica. Para las simulaciones de Monte Carlo, un LCG debe usar un módulo mayor y preferiblemente mucho mayor que el cubo del número de muestras aleatorias que se requieren. Esto significa, por ejemplo, que se puede usar un (buen) LCG de 32 bits para obtener alrededor de mil números aleatorios; un LCG de 64 bits es bueno para aproximadamente 2²¹ muestras aleatorias (un poco más de dos millones), etc. Por esta razón, en la práctica, los LCG no son adecuados para simulaciones de Monte Carlo a gran escala.

Código de muestra

Código Python

La siguiente es una implementación de un LCG en Python, en forma de generador:

desde collections.abc importación Generadordef lcg()modulus: int, a: int, c: int, semillas: int) - Generador[int, Ninguno, Ninguno]: ""Grupo congruencial en línea"" mientras Cierto.: semillas = ()a * semillas + c) % modulus rendimiento semillas

Pascal Libre

Free Pascal usa un Mersenne Twister como su generador de números pseudoaleatorios predeterminado, mientras que Delphi usa un LCG. Aquí hay un ejemplo compatible con Delphi en Free Pascal basado en la información de la tabla anterior. Dado el mismo valor de RandSeed, genera la misma secuencia de números aleatorios que Delphi.

unidad lcg_random;{$ifdef fpc}{$mode delphi}{$endif}interfazfunción LCGRandom: prórroga; sobrecarga; inline;función LCGRandom()const rango:longint): longint; sobrecarga; inline;aplicaciónfunción IM: cardenal; inline;comenzar RandSeed := RandSeed * 134775813 + 1; Resultado := RandSeed;final;función LCGRandom: prórroga; sobrecarga; inline;comenzar Resultado := IM * 2.32830643653870e-10;final;función LCGRandom()const rango: longint): longint; sobrecarga; inline;comenzar Resultado := IM * rango Shr 32;final;

Como todos los generadores de números pseudoaleatorios, un LCG necesita almacenar el estado y modificarlo cada vez que genera un nuevo número. Múltiples hilos pueden acceder a este estado simultáneamente causando una condición de carrera. Las implementaciones deben usar un estado diferente, cada uno con una inicialización única para diferentes subprocesos para evitar secuencias iguales de números aleatorios en subprocesos que se ejecutan simultáneamente.

Derivados de LCG

Hay varios generadores que son generadores lineales congruentes en una forma diferente y, por lo tanto, se les pueden aplicar las técnicas utilizadas para analizar los LCG.

Un método para producir un período más largo es sumar las salidas de varios LCG de diferentes períodos que tengan un mínimo común múltiplo grande; el generador de Wichmann-Hill es un ejemplo de esta forma. (Preferiríamos que fueran completamente coprimos, pero un módulo primo implica un período par, por lo que debe haber un factor común de 2, al menos). Se puede demostrar que esto es equivalente a un único LCG con un módulo igual al producto de los módulos LCG del componente.

PRNG de suma con acarreo y resta con préstamo de Marsaglia con un tamaño de palabra de b=2^w y los retrasos r y s (r > s) son equivalentes a LCG con un módulo de b^r ± b^s ± 1.

Los PRNG de multiplicación con acarreo con un multiplicador de a son equivalentes a los LCG con un módulo primo grande de ab^r−1 y un multiplicador de potencia de 2 b.

Un generador congruencial permutado comienza con un LCG de potencia de módulo 2 y aplica una transformación de salida para eliminar el problema del período corto en los bits de orden inferior.

Comparación con otros PRNG

La otra primitiva ampliamente utilizada para obtener secuencias pseudoaleatorias de período largo es la construcción del registro de desplazamiento de retroalimentación lineal, que se basa en la aritmética en GF(2)[x], el anillo polinomial sobre GF (2). En lugar de la suma y la multiplicación de enteros, las operaciones básicas son la multiplicación exclusiva-o y sin acarreo, que generalmente se implementa como una secuencia de cambios lógicos. Estos tienen la ventaja de que todos sus bits son de período completo; no sufren la debilidad en los bits de bajo orden que afecta a la aritmética módulo 2^k.

Ejemplos de esta familia incluyen generadores xorshift y el tornado Mersenne. Este último proporciona un período muy largo (2¹⁹⁹³⁷−1) y uniformidad variable, pero falla algunas pruebas estadísticas. Los generadores de Fibonacci rezagados también entran en esta categoría; aunque utilizan la suma aritmética, su período está asegurado por un LFSR entre los bits menos significativos.

Es fácil detectar la estructura de un registro de desplazamiento de retroalimentación lineal con las pruebas adecuadas, como la prueba de complejidad lineal implementada en la suite TestU01; una matriz circulante booleana inicializada a partir de bits consecutivos de un LFSR nunca tendrá un rango mayor que el grado del polinomio. Agregar una función de mezcla de salida no lineal (como en xoshiro256** y construcciones de generadores congruentes permutados) puede mejorar en gran medida el rendimiento en las pruebas estadísticas.

Otra estructura para un PRNG es una función de recurrencia muy simple combinada con una poderosa función de mezcla de salida. Esto incluye cifrados de bloques en modo contador y generadores no criptográficos como SplitMix64.

Una estructura similar a los LCG, pero no equivalente, es el generador recursivo múltiple: X_n = (a₁X_n−1 + a₂X_n−2 + ··· + a_kX _n−k) mod m para k ≥ 2. Con módulo primo, esto puede generar períodos de hasta m^k−1, por lo que es una extensión útil de la estructura LCG a períodos más grandes.

Una técnica poderosa para generar números pseudoaleatorios de alta calidad es combinar dos o más PRNG de diferente estructura; la suma de un LFSR y un LCG (como en las construcciones KISS o xorwow) puede funcionar muy bien a algún costo en velocidad.