Ir al contenido

Generador lineal congruencial

De Wikipedia, la enciclopedia libre
Esta es una versión antigua de esta página, editada a las 15:29 12 oct 2020 por InternetArchiveBot (discusión · contribs.). La dirección URL es un enlace permanente a esta versión, que puede ser diferente de la versión actual.
Visualización de la generación de números pseudoaleatorios en el intervalo discreto [0, 8] utilizando un generador lineal congruencial. Las dos filas superiores muestran un generador con m = 9, a = 2 y c = 0 obteniéndose los números mostrados de izquierda a derecha hasta que se obtiene la semilla, y la secuencia repite. Una semilla de valor 1 permite un ciclo de longitud 6 pero una semilla de valor 3 solo permite un ciclo de longitud 2. Utilizando a = 4 y c = 1 (fila inferior) se obtiene un ciclo de longitud 9 para cualquier semilla.

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.[1]​ La teoría que sustenta el proceso es relativamente fácil de entender, el algoritmo en si 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.

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

donde es la secuencia de valores pseudoaleatorios, y

es el "módulo"
es el "multiplicador"
es el "incremento"
es la "semilla" or "valor inicial"

todos los cuales son constantes enteras específicas para el generador. Si c = 0, el generador es llamado frecuentemente un generador congruencial multiplicativo (GCM), o generador de números pseudoaleatorios de Lehmer. Si c ≠ 0, el método es llamado un generador congruencial mezclado.[2]​

Longitud del período

El período de un generador congruencial mezclado general es como máximo su módulo, y para algunos valores específicos del multiplicador "a" este período se reduce considerablemente por debajo de este máximo. El generador congruencial mezclado tendrá un período completo para todas las semillas si y sólo si:[2]​[3]​

  1. y el incremento son primos entre sí,
  2. es divisible entre todos los factores primos de ,
  3. es divisible entre 4 si es divisible entre 4.

Estos tres requerimientos son conocidos como el teorema Hull-Dobell.[4]​[5]​ Aunque los GLCs 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 "c", "m" y "a".[aclaración requerida]

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

Parámetros de uso común

Los GLCs más eficientes tienen un módulo igual a una potencia de 2, siendo más frecuentes m = 232 o m = 264, 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 GLCs 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 232 1664525 1013904223
Borland C/C++ 232 22695477 1 bits 30..16 en rand(), 30..0 en lrand()
glibc (usado por GCC)[7]​ 231 - 1 1103515245 12345 bits 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++[8]​
C99, C11: Suggestion in the ISO/IEC 9899[9]​		 231 1103515245 12345 bits 30..16
Borland Delphi, Virtual Pascal 232 134775813 1 bits 63..32 de (semilla * L)
Turbo Pascal 232 134775813 (0x808840516) 1
Microsoft Visual/Quick C/C++ 232 214013 (343FD16) 2531011 (269EC316) bits 30..16
Microsoft Visual Basic (6 and earlier)[10]​ 224 1140671485 (43FD43FD16) 12820163 (C39EC316)
RtlUniform from Native API[11]​ 231 − 1 2147483629 (7FFFFFED16) 2147483587 (7FFFFFC316)
Apple CarbonLib, C++11's minstd_rand0[12]​ 231 − 1 16807 0 ver MINSTD
C++11's minstd_rand[12]​ 231 − 1 48271 0 ver MINSTD
MMIX by Donald Knuth 264 6364136223846793005 1442695040888963407
Newlib, Musl 264 6364136223846793005 1 bits 63...32
VMS's MTH$RANDOM,[13]​ old versions of glibc 232 69069 (10DCD16) 1
.Random en Java, POSIX [ln]rand48, glibc [ln]rand48[_r] 248 − 1 25214903917 (5DEECE66D16) 11 bits 47...16

random0[14]​[15]​[16]​[17]​[18]​

Si Xn es par, entonces Xn+1 será impar, y vice versa—el bit más bajo oscila a cada paso.

134456 = 2375 8121 28411
POSIX[19]​ [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[20]​ 223 65793 (1010116) 4282663 (41592716) bits 22...8
cc65 232 16843009 (101010116) 826366247 (3141592716) bits 31...16
Anteriormente de uso común: RANDU[6]​ 231   65539 0

Como se puede observar, los GLCs 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 GLCs 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 GLCs 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.

Hiperplanos de un generador lineal congruencial en tres dimensiones

Los GLCs 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 GLCs 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 Xn. 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 bk = m, para un cierto entero k), se repite con periodo de, a lo sumo, bn.

Sin embargo, para varias aplicaciones los GLCs 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 GLCs, 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 (219937 − 1) y uniformidad variada, pero no supera algunas pruebas estadísticas.[21]​ Una implementación común del Mersenne twister , usa un GLC para generar su semilla.[cita requerida]

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,[22]​ 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.[23]​ Dados algunos valores en la secuencia, ciertas técnicas pueden predecir los siguientes valores en la secuencia, no solo para los GLCs, sino también para cualquier otro generador congruencial polinomial.[23]​

Referencias

  1. ↑ "Linear Congruential Generators" por Joe Bolte, Wolfram Demonstrations Project.
  2. ↑ a b Donald E. Knuth (6 de mayo de 2014). Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley Professional. pp. 4-. ISBN 978-0-321-63576-1. 
  3. ↑ Knuth, Donald E. Art of Computer Programming, Volume 2: Seminumerical Algorithms (3ra edición). Addison-Wesley Professional. pp. 17-19. ISBN 978-0-321-63576-1. 
  4. ↑ Hull, T. E.; Dobell, A. R. (1 de enero de 1962). «Random Number Generators». SIAM Review 4 (3): 230-254. doi:10.1137/1004061. Consultado el 26 de junio de 2016. 
  5. ↑ Severance, Frank (2001). System Modeling and Simulation. John Wiley & Sons, Ltd. pp. 86. ISBN 0-471-49694-4. 
  6. ↑ a b Press, William H. (1992). Numerical Recipes en Fortran 77: The Art of Scientific Computing (2nd edición). ISBN 0-521-43064-X. 
  7. ↑ El rand() de la librería C de GNU en stdlib.h usa un GLC simple (de estado único) sólo en caso de que el estado sea declarado como de 8 bytes. Si el estado es más grande (un arreglo), el generador se vuelve un generador de retroalimentación aditiva y el período se incrementa. Véase también el código simplificado que reproduce la secuencia aleatoria de esta librería.
  8. ↑ «A collection of selected pseudorandom number generators with linear structures, K. Entacher, 1997». Consultado el 16 de junio de 2012. 
  9. ↑ «Last public Committee Draft from April 12, 2011, page 346f». Consultado el 21 Dec 2014. 
  10. ↑ «How Visual Basic Generates Pseudo-Random Numbers for the RND Function». Microsoft Support. Microsoft. Consultado el 17 de junio de 2011. 
  11. ↑ A pesar de la documentación hallada en MSDN, RtlUniform usa GLC, y no el algoritmo de Lehmer, implementaciones anteriores a Windows Vista contienen errores, porque el resultado de la multiplicación es truncada a 32 bits antes de la aplicación del operador módulo.
  12. ↑ a b «ISO/IEC 14882:2011». ISO. 2 de septiembre de 2011. Consultado el 3 de septiembre de 2011. 
  13. ↑ GNU Scientific Library: Other random number generators
  14. ↑ Stephen J. Chapman. "Example 6.4 - Random Number Generator". "MATLAB Programming for Engineers". 2015. p. 253-256.
  15. ↑ Stephen J. Chapman. "Example 6.4 - Random Number Generator". "MATLAB Programming with Applications for Engineers". 2012. p. 292-295.
  16. ↑ S. J. Chapman. random0. 2004.
  17. ↑ Stephen J. Chapman. "Introduction to Fortran 90/95". 1998. p. 322-324.
  18. ↑ Wu-ting Tsai. "'Module': A Major Feature of the Modern Fortran". p. 6-7.
  19. ↑ The Open Group Base Specifications Issue 7 IEEE Std 1003.1, 2013 Edition
  20. ↑ Cadot, Sidney. «rand.s». cc65. Consultado el 8 de julio de 2016. 
  21. ↑ Matsumoto, Makoto, and Takuji Nishimura (1998) ACM Transactions on Modeling and Computer Simulation 8
  22. ↑ * Neil Gershenfeld. The Nature of Mathematical Modeling, Primera Edición. Cambridge University Press, 1999. ISBN 0-521-57095-6. Sección 5.3.2: Linear Feedback, p. 59.
  23. ↑ a b RFC 4086 Sección 6.1.3 "Traditional Pseudo-random Sequences"
Obtenido de «https://es.wikipedia.org/w/index.php?title=Generador_lineal_congruencial&oldid=130012417»