Generador lineal congruencial
# Generador lineal congruencial

Un generador lineal congruencial (GLC) es un algoritmo que permite obtener una secuencia de números pseudoaleatorios calculados con una función lineal definida a trozos discontinua. Es uno de los métodos más antiguos y conocidos para la generación de números pseudoaleatorios. La teoría que sustenta el proceso es relativamente fácil de entender, el algoritmo en sí es de fácil implementación y su ejecución es rápida, especialmente cuando el hardware del ordenador puede soportar aritmética modular al truncar el bit de almacenamiento correspondiente.

## Definición

La secuencia de números enteros $X_{1},X_{2},X_{3},\dots$ está definida por la relación de recurrencia:

    $X_{i}=\left(aX_{i-1}+c\right){\bmod {m}}$

con $0\leq X_{i}\leq m-1$ donde $m$ (el módulo), $a$ (el multiplicador), $c$ (el incremento) y $X_{0}$ (la semilla o valor inicial) son números enteros no negativos.

Además a los números $m,a,c$ y $X_{0}$ se les impone las condiciones $m>0$, $0<a<m$, $0\leq c<m$ y $0\leq X_{0}<m$.

Si $c=0$, el generador es llamado frecuentemente Generador Congruencial Lineal Multiplicativo (GLMC) o generador de números pseudoaleatorios de Lehmer pero si $c\neq 0$, el generador es llamado Generador Congruencial Lineal Mixto (GLMC).

Cada entero $X_{i}$ queda completamente determinado por las constantes $m,a,c$ y $X_{0}$ pues puede demostrarse por inducción matemática que para $i=1,2,3,\dots$

    $X_{i}=\left[a^{i}X_{0}+{\frac {c(a^{i}-1)}{a-1}}\right]{\bmod {m}}$

## Periodo

Se dice que un generador congruencial cumple un ciclo cuando el número entero $X_{i}$, con $1\leq i\leq m$, coincide con la semilla $X_{0}$, cuando sucede esto, la secuencia de números generados se repetirá en el mismo orden.

El período de un generador congruencial se define como la longitud de un ciclo y dado que $X_{i}$ depende de $X_{i-1}$ y $0\leq X_{i}\leq m-1$ entonces el periodo máximo puede ser a lo más su módulo $m$ y en tal caso diremos que el generador congruencial tiene un periodo completo.

Si un generador congruencial tiene un periodo completo entonces para cualquier valor que tome la semilla $X_{0}$ en $\{0,1,\dots ,m-1\}$ producirá un ciclo en algún orden pero si el generador no tiene un periodo completo, esto es, su periodo es menor a $m$ entonces la longitud del ciclo dependerá del valor escogido de la semilla $X_{0}$.

### Teorema

El generador congruencial lineal dado por

    $X_{i}=\left(aX_{i-1}+c\right){\bmod {m}}$

tendrá período completo $m$ para cualquier valor de la semilla $X_{0}$ en $\{0,1,\dots ,m-1\}$ si y sólo si:

* $c$ y $m$ son primos relativos, es decir, $\operatorname {mcd} (c,m)=1$.
* $\,a-1$ es múltiplo de todos los factores primos de $m$, es decir, $a\equiv 1{\bmod {q}}$ para todo $q$ factor primo de $m$.
* Si $m$ es múltiplo de $4$ entonces $a-1$ también lo es, es decir, $m\equiv 0{\bmod {4}}\Longleftrightarrow a\equiv 1{\bmod {4}}$.

Estas tres condiciones son conocidas como el Teorema Hull-Dobell.

El Generador Congruencial Lineal Multiplicativo (GLMC) no cumple la primera condición, pues $\operatorname {mcd} (0,m)=m$, por lo que no tienen periodo completo $m$.

Aunque los GLC son capaces de producir números pseudoaleatorios que pueden pasar las pruebas de aleatoriedad, esta posibilidad es extremadamente sensible a la elección de los parámetros $m,a$ y $c$.

Históricamente, elecciones inadecuadas llevaron a implementaciones inefectivas de GLC. Un ejemplo que ilustra esta situación es el generador RANDU, que fue ampliamente utilizado a inicios de los 1970, y ha llevado a que en la actualidad, varios resultados sean puestos en entredicho por el uso de este GLC inefectivo.

## Parámetros de uso común

Los GLC más eficientes tienen un módulo igual a una potencia de 2, siendo más frecuentes $m=2^{32}$ o $m=2^{64}$, porque esto permite que el operador módulo opere tan solo truncando todos los bits excepto los 32 o 64 bits más cercanos a la derecha (de hecho, esto puede lograrse simplemente al no computar en absoluto los bits más significativos). La siguiente tabla enlista los parámetros de varios GLC comúnmente usados, incluyendo las funciones "rand" presentes en las bibliotecas runtime de varios compiladores.

| Fuente | m | (multiplicador) a | (incremento) c | Bits de salida en rand o Random(L) |
| - | - | - | - | - |
| Numerical Recipes | $2^{32}$ | 1664525 | 1013904223 | |
| Borland C/C++ | $2^{32}$ | 22695477 | 1 | bits 30..16 en rand, 30..0 en lrand |
| glibc (usado por GCC) | $2^{31}$ - 1 | 1103515245 | 12345 | bits 30..0 |
| ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ C99, C11: Suggestion in the ISO/IEC 9899 | $2^{31}$ | 1103515245 | 12345 | bits 30..16 |
| Borland Delphi, Virtual Pascal | $2^{32}$ | 134775813 | 1 | bits 63..32 de (semilla * L) |
| Turbo Pascal | $2^{32}$ | 134775813 $(0x8088405_{16})$ | 1 | |
| Microsoft Visual/Quick C/C++ | $2^{32}$ | 214013 $(343FD_{16})$ | 2531011 $(269EC3_{16})$ | bits 30..16 |
| Microsoft Visual Basic (6 and earlier) | $2^{24}$ | 1140671485 $(43FD43FD_{16})$ | 12820163 $(C39EC3_{16})$ | |
| RtlUniform from Native API | $2^{31}$ − 1 | 2147483629 $(7FFFFFED_{16})$ | 2147483587 $(7FFFFFC3_{16})$ | |
| Apple CarbonLib, C++11's minstd_rand0 | $2^{31}$ − 1 | 16807 | 0 | ver MINSTD |
| C++11's minstd_rand | $2^{31}$ − 1 | 48271 | 0 | ver MINSTD |
| MMIX by Donald Knuth | $2^{64}$ | 6364136223846793005 | 1442695040888963407 | |
| Newlib, Musl | $2^{64}$ | 6364136223846793005 | 1 | bits 63...32 |
| VMS's MTH$RANDOM, old versions of glibc | $2^{32}$ | 69069 $(10DCD_{16})$ | 1 | |
| .Random en Java, POSIX [ln]rand48, glibc [ln]rand48[_r] | $2^{48}$ − 1 | 25214903917 $(5DEECE66D_{16})$ | 11 | bits 47...16 |
| random0 Si $X_n$ es par, entonces $X_{n+1}$ será impar, y viceversa—el bit más bajo oscila a cada paso. | 134456 = $2^37^5$ | 8121 | 28411 | ${\frac {X_{n}}{134456}}$ |
| POSIX [jm]rand48, glibc [mj]rand48[_r] | $2^{48}$ | 25214903917 $(5DEECE66D_{16})$ | 11 | bits 47...15 |
| POSIX [de]rand48, glibc [de]rand48[_r] | $2^{48}$ | 25214903917 $(5DEECE66D_{16})$ | 11 | bits 47...0 |
| cc65 | $2^{23}$ | 65793 $(10101_{16})$ | 4282663 $(415927_{16})$ | bits 22...8 |
| cc65 | $2^{32}$ | 16843009 $(1010101_{16})$ | 826366247 $(31415927_{16})$ | bits 31...16 |
| Anteriormente de uso común: RANDU | $2^{31}$ | 65539 | 0 | |

Como se puede observar, los GLC no siempre usan todos los bits en el valor que producen. Por ejemplo, la implementación de Java opera con valores de $48$ bits en cada iteración, pero solo retorna los $32$ bits más significativos. Esto se debe a que los bits superiores tienen periodos más largos que los inferiores (ver más abajo). Los GLC que usan esta técnica de truncado producen valores estadísticamente mejores en comparación a aquellos que no lo hacen.

## Ventajas y desventajas

Los GLC son rápidos, y requieren poca memoria (normalmente 32 o 64 bits) para retener su estado. Esto los hace valiosos para simular flujos múltiples.

Los GLC no deberían ser usados en aplicaciones para las que se requiera aleatoriedad de alta calidad. Por ejemplo, esta técnica es inadecuada para el uso en una simulación de Monte Carlo debido a la correlación serial de la secuencia (entre otros motivos). Tampoco deberían usarse para aplicaciones criptográficas; ejemplos de generadores más adecuados para esta función se pueden encontrar en Generador de números pseudoaleatorios criptográficamente seguro. Si un GLC es sembrado con un carácter e iterado una única vez, el resultado es un sencillo cifrado afín clásico, el cual puede ser descifrado con un análisis de frecuencia estándar.

Los GLC tienden a exhibir severos defectos. Por ejemplo, si un GLC es usado para elegir puntos en un espacio n-dimensional, los puntos yacerán ,a lo sumo, sobre $(n!m)^{1/n}$ hiperplanos (teorema desarrollado por George Marsaglia). Esto se debe a la correlación serial entre valores sucesivos en la secuencia $X_n.$ La prueba espectral, la cual es una simple evaluación de la calidad de un GLC, está basada en este hecho.

Otro inconveniente del uso de esta técnica es que los bits de menor valor de la secuencia generada tienen un periodo mucho menor a la secuencia como un todo, si a $m$ le es asignado una potencia de 2. En términos generales, el bit menos significativo, ocupando el lugar $n$ en base $b$ en la secuencia de salida (tal que $b^{k}=m$ para un cierto entero $k$), se repite con periodo de, a lo sumo, $b^{n}$.

Sin embargo, para varias aplicaciones los GLC son una buena opción. Un ejemplo puede verse en los sistemas embebidos, en los que la memoria disponible se ve severamente limitada. De manera similar, en un ambiente como una consola de videojuegos puede bastar referirse a los bits más significativos de la secuencia de salida. Los bits de menor orden de un GLC no deberían ser usados para ningún nivel de aleatoriedad si el valor m de dicho generador es una potencia de dos. En particular, cualquier GLC de ciclo completo cuando m es una potencia de 2 producirá alternativamente resultados pares e impares.

## Comparación con otros generadores de números pseudoaleatorios

Los generadores basados en recurrencias lineales (como xorshift*) superan el desempeño de los GLC, incluso para un número total de estados pequeño, y si son adecuadamente perturbados en la señal de salida, pueden superar pruebas estadísticas difíciles. Varios ejemplos pueden encontrarse en la familia de generadores Xorshift.

El algoritmo Mersenne twister provee un periodo largo $(2^{19937}-1)$ y uniformidad variada, pero no supera algunas pruebas estadísticas. Una implementación común del Mersenne twister, usa un GLC para generar su semilla.

Los generadores lineales congruenciales presentan el inconveniente de generar secuencias de salida cuyos bits presentan distintos niveles de aleatoriedad. Un generador que haga uso de un registro de desplazamiento con retroalimentación lineal produce un flujo de bits, cada uno realmente pseudoaleatorio, y puede ser implementado en esencia, con la misma cantidad de memoria que un GLC, aunque usando más cómputos.

El registro de desplazamiento con retroalimentación lineal tiene una fuerte relación con los GLCs. Dados algunos valores en la secuencia, ciertas técnicas pueden predecir los siguientes valores en la secuencia, no solo para los GLC, sino también para cualquier otro generador congruencial polinomial.

