Hispanopedia Wiki
Articulo de referencia

Generador congruencial lineal

Dos LCG módulo 9 muestran cómo diferentes parámetros conducen a diferentes longitudes de ciclo. Cada fila muestra el estado evolucionando hasta repetirse. La fila superior muest...

Hispanopedia WikiContenido en espanolLectura gratuita
Dos LCG módulo 9 muestran cómo diferentes parámetros conducen a diferentes longitudes de ciclo. Cada fila muestra el estado evolucionando hasta repetirse. 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. Usando a  =  4 y c  =  1 (fila inferior) se obtiene una longitud de ciclo de 9 con cualquier semilla en [0,  8].

Un generador congruencial lineal ( LCG ) es un algoritmo que produce una secuencia de números pseudoaleatorios calculados mediante una ecuación lineal a trozos discontinua. Este método representa uno de los algoritmos de generación de números pseudoaleatorios más antiguos y conocidos . Su teoría es relativamente fácil de comprender, y su implementación es sencilla y rápida, especialmente en hardware informático que permite la aritmética modular mediante truncamiento de bits de almacenamiento.

El generador se define mediante la relación de recurrencia :

incógnitanorte+1=(aincógnitanorte+do)modmetro{\displaystyle X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}}

dóndeincógnita{\displaystyle X}es la secuencia de valores pseudoaleatorios, y

metro,0<metro{\displaystyle m,\,0<m}— el " módulo "
a,0<a<metro{\displaystyle a,\,0<a<m}— el "multiplicador"
do,0≤do<metro{\displaystyle c,\,0\leq c<m}— el "incremento"
incógnita0,0≤incógnita0<metro{\displaystyle X_{0},\,0\leq X_{0}<m}— el "valor 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 generador de números aleatorios de Lehmer . Si c  ≠  0, el método se denomina generador congruencial mixto . [ 1 ] : 4-

Cuando c  ≠  0, un matemático llamaría a la recurrencia una transformación afín , no lineal , pero el término erróneo está bien establecido en la informática. [ 2 ] : 1

Historia

El generador de Lehmer fue publicado en 1951 [ 3 ] y el generador congruencial lineal fue publicado en 1958 por WE Thomson y A. Rotenberg. [ 4 ] [ 5 ]

duración del período

Una ventaja de los LCG es que una selección adecuada de parámetros da como resultado un período conocido y prolongado. Si bien no es el único criterio, un período demasiado corto constituye un defecto fatal en un generador de números pseudoaleatorios. [ 6 ]

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 . [ 1 ] [ 2 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] Por ejemplo, a  =  1 y c  =  1 producen un contador simple módulo m , que tiene un período largo, pero obviamente no es aleatorio. Otros valores de c coprimo con m producen una secuencia de Weyl , que está mejor distribuida pero sigue siendo obviamente no aleatoria.

Históricamente, las malas decisiones en cuanto a la elección de un modelo han dado lugar a implementaciones ineficaces de los LCG. Un ejemplo particularmente ilustrativo de esto es RANDU , que se utilizó ampliamente a principios de la década de 1970 y produjo muchos resultados que actualmente se cuestionan debido al uso de este LCG deficiente. [ 11 ] [ 8 ] : 1198–9

Existen tres familias comunes de selección de parámetros:

m prima, c = 0

Esta es la construcción original del generador de números aleatorios 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 utiliza un primo ligeramente menor que una potencia de 2 (los primos de Mersenne 2 31 −1 y 2 61 −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 ⌊ ax /2 e ⌋ . A esto debe seguir 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 no se dispone de un producto de doble ancho y el multiplicador se elige cuidadosamente, se puede utilizar el método de Schrage [ 12 ] [ 13 ] . Para ello, 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 a se elige 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 pueden calcularse con un producto de ancho simple, y la diferencia entre ellos se encuentra en el rango [1− m , m −1], por lo que puede reducirse a [0, m −1] con una sola suma condicional. [ 14 ]             

La operación más costosa en el método de Schrage es la división (con resto) de x entre q ; no existen algoritmos rápidos para la división por una constante, ya que también dependen de productos de doble ancho.

Una segunda desventaja de usar un módulo primo es que resulta complicado convertir el valor 1  ≤ x < m a bits aleatorios uniformes. Si se utiliza un número primo ligeramente menor que una potencia de 2, a veces los valores faltantes simplemente se ignoran.   

m una potencia de 2, c = 0

Elegir m como una potencia de dos , generalmente m = 2³² o m = 2⁶⁴ , produce una LCG particularmente eficiente, ya que esto permite calcular el módulo simplemente truncando la representación binaria. De hecho, los bits más significativos generalmente no se calculan en absoluto. Sin embargo, existen desventajas.

Esta forma tiene un período máximo m /4, que se alcanza si a  ≡  ±3 (mod 8) y el estado inicial X₀ es impar. Incluso en este mejor caso, los tres bits menos significativos de X alternan entre dos valores y, por lo tanto , solo contribuyen con un bit al estado. X siempre es impar (el bit de menor orden nunca cambia), y solo uno de los dos bits siguientes cambia. Si a ≡ +3, X alterna ±1↔±3, mientras que si a ≡ −3, X alterna ±1↔∓3 (todo módulo 8).    

Se puede demostrar que esta forma es equivalente a un generador con módulo m /4 y c ≠ 0. [ 1 ]

Un problema más serio con el uso de un módulo potencia de dos es que los bits bajos tienen un período más corto que los bits altos. Su simplicidad de implementación proviene del hecho de que los bits nunca se ven afectados por los bits de orden superior, por lo que los bits bajos b de dicho generador forman por sí mismos un LCG módulo 2 b , que se repite con un período de 2 b −2 . Solo el bit más significativo de X alcanza el período completo.

m una potencia de 2, c ≠ 0

Cuando c ≠ 0, los parámetros elegidos correctamente permiten un período igual a m , para todos los valores de semilla. Esto ocurrirá si y solo si : [ 1 ] : 17–19

  1. metro{\displaystyle m}ydo{\displaystyle c}son coprimos,
  2. a−1{\displaystyle a-1}es divisible por todos los factores primos demetro{\displaystyle m},
  3. a−1{\displaystyle a-1}es divisible por 4 simetro{\displaystyle m}es divisible por 4.

Estos tres requisitos se conocen como el Teorema de Hull-Dobell. [ 15 ] [ 16 ]

Esta forma puede usarse 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 la computadora es la opción más común. Si m fuera un entero libre de cuadrados , esto solo permitiría a  ≡  1 (mod m ), lo que resulta en un generador de números pseudoaleatorios muy deficiente; 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. [ 8 ] : 1199 Por ejemplo, es deseable que a  −  1 no sea divisible por factores primos de m más de lo necesario. 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). [ 1 ] : §3.2.1.3     

De hecho, la mayoría de los multiplicadores producen una secuencia que no supera una prueba de no aleatoriedad u otra, y encontrar un multiplicador que sea satisfactorio para todos los criterios aplicables [ 1 ] : §3.3.3 es bastante difícil. [ 8 ] La prueba espectral es una de las pruebas más importantes. [ 17 ]

Nótese que un módulo potencia de 2 comparte el problema descrito anteriormente para c  = 0: los k  bits bajos forman un generador con módulo 2k y , por lo tanto, se repiten con un período de 2k ; solo el bit más significativo alcanza el período completo. Si se desea un número pseudoaleatorio menor que r , ⌊ rX / m ⌋ 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 ( ), por lo que se usa con mucha frecuencia.X % r

El generador no es sensible a la elección de c , siempre que sea relativamente primo con el 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 secuencia producida por otras elecciones de c puede escribirse como una función simple de la secuencia cuando c = 1. [ 1 ] : 11 Específicamente, si Y es la secuencia prototípica definida por Y 0 =  0 y Y n + 1 = aY n + 1 mod m, entonces una secuencia general X n + 1 = aX n + c mod m puede escribirse como una función afín de Y :        

incógnitanorte=(incógnita0(a−1)+do)Ynorte+incógnita0=(incógnita1−incógnita0)Ynorte+incógnita0(modmetro).{\displaystyle X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.}

De forma más general, cualesquiera dos secuencias X y Z con el mismo multiplicador y módulo están relacionadas por

incógnitanorte−incógnita0incógnita1−incógnita0=Ynorte=anorte−1a−1=Znorte−Z0Z1−Z0(modmetro).{\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}}.}

En el caso común donde m es una potencia de 2 y a  ≡  5  (mod  8) (una propiedad deseable por otras razones), siempre es posible encontrar un valor inicial X 0 tal que el denominador X 1  − X 0 ≡ ±1 (mod m ), produciendo una relación aún más simple. Con esta elección de X 0 , X n = X 0 ± Y n seguirá siendo verdadero para todo n . [ 2 ] : 10-11 El signo está determinado por c ≡ ±1 (mod 4), y la constante X 0 está determinada por 1 ∓ c ≡ (1 − a ) X 0 (mod m ).                   

Como ejemplo sencillo, consideremos los generadores X n +1 =  157 X n  +  3 mod  256 y Y n +1 =  157 Y n  +  1 mod  256; es decir, m  =  256, a  =  157 y c  =  3. Dado que 3  ≡  −1  (mod  4), estamos buscando una solución para 1  +  3  ≡  (1  −  157) X 0  (mod  256). Esto se satisface con X 0  ≡  41  (mod  64), por lo que si comenzamos con eso, entonces X n ≡ X 0 − Y n (mod 256) para todo n .     

Por ejemplo, usando X 0 = 233 = 3 × 64 + 41:

  • X = 233, 232, 75, 2, 61, 108, ...
  • Y = 0, 1, 158, 231, 172, 125, ...
  • X  + Y mod 256 = 233, 233, 233, 233, 233, 233, ... 

Parámetros de uso común

La siguiente tabla enumera los parámetros de los generadores de conglomerados lineales (LCG) de uso común, incluidas las funciones rand() integradas en las bibliotecas de tiempo de ejecución de varios compiladores . Esta tabla muestra la popularidad de los LCG, no ejemplos para emular; muchos de estos parámetros son deficientes. Existen tablas con parámetros adecuados. [ 10 ] [ 2 ]

Como se muestra arriba, los LCG no siempre utilizan todos los bits de los valores que producen. En general, devuelven los bits más significativos. Por ejemplo, la implementación en Java opera con valores de 48 bits en cada iteración, pero devuelve solo sus 32 bits más significativos. Esto se debe a que los bits de orden superior tienen periodos más largos que los de orden inferior (véase más abajo). Los LCG que utilizan esta técnica de truncamiento producen valores estadísticamente mejores que los que no la utilizan. Esto se nota especialmente en los scripts que usan la operación módulo para reducir el rango; modificar el número aleatorio módulo 2 dará como resultado una alternancia de 0 y 1 sin truncamiento.

Por el contrario, algunas bibliotecas utilizan un módulo implícito que es potencia de dos, pero nunca generan ni utilizan el bit más significativo, con el fin de limitar la salida a enteros positivos en complemento a dos . La salida es como si el módulo fuera un bit menor que el tamaño de palabra interno, y estos generadores se describen como tales en la tabla anterior.

Ventajas y desventajas

Los generadores de números aleatorios locales (LCG) son rápidos y requieren una memoria mínima (un número módulo m , generalmente de 32 o 64 bits) para conservar su estado. Esto los hace valiosos para simular múltiples flujos independientes. Los LCG no están diseñados para aplicaciones criptográficas y no deben utilizarse para ellas; para tales aplicaciones, utilice un generador de números pseudoaleatorios criptográficamente seguro .

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

Aunque los LCG tienen algunas debilidades específicas, muchos de sus defectos provienen de tener un estado demasiado pequeño. El hecho de que durante tantos años se haya confiado en su uso con módulos tan pequeños puede considerarse una prueba de la solidez de la técnica. Un LCG con un estado suficientemente grande puede superar incluso pruebas estadísticas rigurosas; un LCG de módulo 2 de 64 bits que devuelve los 32 bits superiores supera la suite SmallCrush de TestU01 , y un LCG de 96 bits supera la suite BigCrush, la más rigurosa. [ 39 ]

Como ejemplo específico, se espera que un generador de números aleatorios ideal con una salida de 32 bits (según el teorema del cumpleaños ) comience a duplicar las salidas anteriores después de √ m ≈ 2 16 resultados. Cualquier PRNG cuya salida sea su estado completo y sin truncar no producirá duplicados hasta que transcurra su período completo, un defecto estadístico fácilmente detectable. [ 40 ] Por razones relacionadas, cualquier PRNG debería tener un período mayor que el cuadrado del número de salidas requeridas. Dada la velocidad de las computadoras modernas, esto significa un período de 2 64 para todas las aplicaciones excepto las menos exigentes, y mayor para simulaciones exigentes.

Un defecto específico de los LCG es que, si se usan para elegir puntos en un espacio n-dimensional, los puntos estarán situados, como máximo, en n √ n !⋅ m hiperplanos ( teorema de Marsaglia , desarrollado por George Marsaglia ). [ 7 ] Esto se debe a la correlación serial entre valores sucesivos de la secuencia X n . Los multiplicadores elegidos descuidadamente generalmente tendrán muchos menos planos, ampliamente 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.

El espaciado entre planos depende tanto del módulo como del multiplicador. Un módulo 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. Aún es necesario calcular el índice espectral y asegurarse de que el multiplicador no sea malo, pero, desde un punto de vista puramente probabilístico, 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 corto período de los bits de orden inferior cuando m se elige como una potencia de 2. En particular, cualquier LCG de ciclo completo, cuando m es una potencia de 2, producirá resultados pares e impares alternativamente. Esto se puede mitigar utilizando un módulo mayor que la salida requerida y empleando los bits más significativos del estado.

No obstante, para algunas aplicaciones, los LCG pueden ser una buena opción. Por ejemplo, en un sistema embebido, la cantidad de memoria disponible suele ser muy limitada. Del mismo modo, en un entorno como una consola de videojuegos, utilizar un pequeño número de bits de orden superior de un LCG puede ser suficiente. (Como se mencionó anteriormente, nunca se debe confiar en los bits de orden inferior de los LCG cuando m es una potencia de 2 para obtener ningún grado de aleatoriedad).

Los generadores de números aleatorios locales (LCG) deben evaluarse cuidadosamente para determinar su idoneidad en aplicaciones no criptográficas donde la aleatoriedad de alta calidad es fundamental. Para simulaciones de Monte Carlo, un LCG debe utilizar un módulo mayor, y preferiblemente mucho mayor, que el cubo del número de muestras aleatorias requeridas. Esto significa, por ejemplo, que un LCG de 32 bits (de buena calidad) puede utilizarse para obtener alrededor de mil números aleatorios; un LCG de 64 bits es adecuado 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 ejemplo

Código Python

A continuación se muestra una implementación de un LCG en Python , en forma de generador :

from collections.abc import Generatordef lcg ( módulo : int , a : int , c : int , semilla : int ) -> Generador [ int , Ninguno , Ninguno ]: """Generador congruencial lineal.""" while True : semilla = ( a * semilla + c ) % módulo produce semilla

Código Haskell

A continuación se muestra una implementación de un LCG en Haskell que utiliza una estrategia de evaluación perezosa para generar un flujo infinito de valores de salida en una lista:

-- Permitiendo una elección genérica para a, c, m y x_0 linearCongruentialGenerator :: Integer -> Integer -> Integer -> Integer -> [ Integer ] linearCongruentialGenerator a c módulo semilla = lcgacmx0 donde lcgacmx0 = semilla : map ( \ x -> ( a * x + c ) ` mod ` módulo ) lcgacmx0-- Los parámetros específicos se pueden especificar fácilmente (por ejemplo, los parámetros MMIX de Knuth): mmixLCG :: Integer -> [ Integer ] mmixLCG = linearCongruentialGenerator 6364136223846793005 1442695040888963407 ( 2 ^ ( 64 :: Integer ))

Pascal libre

Free Pascal utiliza un Mersenne Twister como generador de números pseudoaleatorios predeterminado, mientras que Delphi utiliza un LCG. Aquí se muestra un ejemplo compatible con Delphi en Free Pascal, basado en la información de la tabla anterior. Con 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 : extendida ; sobrecarga ; en línea ; función LCGRandom ( const rango : longint ) : longint ; sobrecarga ; en línea ;función de implementación IM : cardinal ; inline ; begin RandSeed := RandSeed * 134775813 + 1 ; Result := RandSeed ; end ;función LCGRandom : extendida ; sobrecarga ; en línea ; inicio Resultado := IM * 2.32830643653870e-10 ; fin ;función LCGRandom ( const range : longint ) : longint ; sobrecarga ; en línea ; inicio Resultado := IM * rango shr 32 ; fin ;

Como todos los generadores de números pseudoaleatorios, un LCG necesita almacenar un estado y modificarlo cada vez que genera un nuevo número. Varios hilos pueden acceder a este estado simultáneamente, lo que provoca una condición de carrera. Las implementaciones deben usar estados diferentes, cada uno con una inicialización única para cada hilo, a fin de evitar secuencias idénticas de números aleatorios en hilos que se ejecutan simultáneamente.

derivados de LCG

Existen varios generadores que son generadores congruenciales lineales en una forma diferente, por lo que las técnicas utilizadas para analizar los LCG se pueden aplicar a ellos.

Un método para generar un período más largo consiste en sumar las salidas de varias LCG de períodos diferentes que tengan un múltiplo mínimo común 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 al menos un factor común de 2). Se puede demostrar que esto es equivalente a una única LCG con un módulo igual al producto de los módulos de las LCG componentes.

Los PRNG de suma con acarreo y resta con préstamo de Marsaglia con un tamaño de palabra de b = 2w y retardos r y s ( r  > s ) son equivalentes a LCG con un módulo de b r ± b s ± 1. [ 41 ] [ 42 ]     

Los PRNG de multiplicación con acarreo con un multiplicador de a son equivalentes a 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 módulo potencia de 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 generadores de números pseudoaleatorios

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

Ejemplos de esta familia incluyen los generadores xorshift y el Mersenne twister . Este último proporciona un período muy largo (2 19937 −1) y uniformidad de varianza, pero no supera algunas pruebas estadísticas. [ 44 ] Los generadores de Fibonacci retardados también pertenecen a esta categoría; aunque utilizan la suma aritmética, su período está garantizado por un LFSR entre los bits menos significativos.

Es fácil detectar la estructura de un registro de desplazamiento con retroalimentación lineal mediante pruebas apropiadas [ 45 ] , como la prueba de complejidad lineal implementada en el conjunto de pruebas 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 las construcciones xoshiro256** y generador congruencial permutado ) puede mejorar considerablemente el rendimiento en las pruebas estadísticas.

Otra estructura para un generador de números pseudoaleatorios (PRNG) es una función de recurrencia muy simple combinada con una potente 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 1 X n −1  + a 2 X n −2  + ···  + a k X n − k ) mod m para k ≥ 2. Con un 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 eficaz para generar números pseudoaleatorios de alta calidad consiste en combinar dos o más generadores de números pseudoaleatorios (PRNG) de diferente estructura; la suma de un LFSR y un LCG (como en las construcciones KISS o xorwow ) puede funcionar muy bien, aunque a costa de una menor velocidad.

Véase también

Notas

  1. 1 2 3 4 5 6 7 Knuth, Donald (1997). Algoritmos seminuméricos . El arte de la programación informática . Vol.  2 (3.ª  ed.). Reading, MA: Addison-Wesley Professional. pp. 10–26 . 
  2. 1 2 3 4 Steele, Guy L. Jr. ; Vigna, Sebastiano (febrero de 2022) [15 de enero de 2020]. "Multiplicadores computacionalmente fáciles y espectralmente buenos para generadores de números pseudoaleatorios congruenciales" . Software: Practice and Experience . 52 (2): 443– 458. arXiv : 2001.05304 . doi : 10.1002/spe.3030 . hdl : 2434/891395 . estas denominaciones, utilizadas ya durante medio siglo, son completamente erróneas desde un punto de vista matemático... En este punto es improbable que se corrijan los nombres ahora tradicionales.Software y datos asociados en https://github.com/vigna/CPRNG .
  3. ↑ Lehmer, Derrick H. (1951). "Métodos matemáticos en unidades de computación a gran escala". Actas del 2.º Simposio sobre Maquinaria de Cálculo Digital a Gran Escala : 141–146 .
  4. ↑ Thomson, WE (1958). "Un método de congruencia modificado para generar números pseudoaleatorios" . The Computer Journal . 1 (2): 83. doi : 10.1093/comjnl/1.2.83 .
  5. ↑ Rotenberg, A. (1960). "Un nuevo generador de números pseudoaleatorios" . Journal of the ACM . 7 (1): 75– 77. doi : 10.1145/321008.321019 . S2CID 16770825 . 
  6. ↑ L'Ecuyer, Pierre (13 de julio de 2017). Chan, WKV; D'Ambrogio, A.; Zacharewicz, G.; Mustafee, N.; Wainer, G.; Page, E. (eds.). Historia de la generación uniforme de números aleatorios (PDF) . Actas de la Conferencia de Simulación de Invierno de 2017 (en prensa). Las Vegas, Estados Unidos. hal-01561551 .
  7. 1 2 Marsaglia, George (septiembre de 1968). "Los números aleatorios caen principalmente en los planos" (PDF) . PNAS . 61 (1): 25– 28. Bibcode : 1968PNAS...61...25M . doi : 10.1073/ pnas.61.1.25 . PMC 285899. PMID 16591687 .  
  8. 1 2 3 4 Park, Stephen K.; Miller, Keith W. (octubre de 1988). "Generadores de números aleatorios: los buenos son difíciles de encontrar" (PDF) . Communications of the ACM . 31 (10): 1192– 1201. doi : 10.1145/63039.63042 . S2CID 207575300. En cierto sentido , es lamentable que esta prueba para el período completo sea tan trivial, ya que alienta falsamente a los no especialistas a construir sus propios generadores. 
  9. ↑ Hörmann, Wolfgang; Derflinger, Gerhard (1993). "Un generador portátil de números aleatorios uniformes muy adecuado para el método de rechazo" ( PDF) . ACM Transactions on Mathematical Software . 19 (4): 489– 495. CiteSeerX 10.1.1.52.3811 . doi : 10.1145/168173.168414 . S2CID 15238956. un multiplicador tan pequeño como √ m , produce números aleatorios con una mala distribución unidimensional.  
  10. 1 2 L'Ecuyer, Pierre (enero de 1999). "Tablas de generadores congruenciales lineales de diferentes tamaños y buena estructura reticular" (PDF) . Matemáticas de la computación . 68 (225): 249– 260. Bibcode : 1999MaCom..68..249L . CiteSeerX 10.1.1.34.1024 . doi : 10.1090/S0025-5718-99-00996-5 .  Asegúrese de leer también las erratas .
  11. 1 2 Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2.ª ed.). Cambridge University Press. pág. 268. ISBN    978-0-521-43064-7.
  12. ↑ Schrage, Linus (junio de 1979). "Un generador de números aleatorios Fortran más portátil" (PDF) . ACM Transactions on Mathematical Software . 5 (2): 132– 138. doi : 10.1145/355826.355828 .
  13. ↑ Jain, Raj (9 de julio de 2010). "Análisis del rendimiento de sistemas informáticos Capítulo 26: Generación de números aleatorios" (PDF) . págs. 19–20 . Recuperado el 31 de octubre de 2017 . 
  14. ↑ Fenerty, Paul (11 de septiembre de 2006). "El método de Schrage" . Archivado del original el 30 de diciembre de 2018. Recuperado el 31 de octubre de 2017 .
  15. ↑ Hull, TE; Dobell, AR (julio de 1962). "Generadores de números aleatorios" (PDF) . SIAM Review . 4 (3): 230– 254. Bibcode : 1962SIAMR...4..230H . doi : 10.1137/1004061 . hdl : 1828/3142 . Consultado el 26 de junio de 2016 .
  16. ↑ Severance, Frank (2001). Modelado y simulación de sistemas . John Wiley & Sons, Ltd. pág. 86. ISBN  978-0-471-49694-6.
  17. ↑ Austin, David (marzo de 2008). "Números aleatorios: nada al azar" . Columna de opinión . Sociedad Matemática Americana.
  18. ↑ "SINCLAIR ZX SPECTRUM - Programación BASIC, capítulo 11" . Consultado el 14 de marzo de 2025 .
  19. ↑ Implementación en la versión glibc-2.26. Consulte el código después de la prueba para "TYPE_0"; la función rand() de la biblioteca GNU C en stdlib.h utiliza un generador congruencial lineal simple (de un solo estado) solo si el estado se declara como 8 bytes. Si el estado es mayor (un array), el generador se convierte en un generador de retroalimentación aditiva ( inicializado con minstd_rand0 ) y el período aumenta. Consulte el código simplificado que reproduce la secuencia aleatoria de esta biblioteca.
  20. ↑ K. Entacher (21 de agosto de 1997). Una colección de generadores de números pseudoaleatorios seleccionados con estructuras lineales . CiteSeerX 10.1.1.53.3686 . Recuperado el 16 de junio de 2012 . 
  21. ↑ "Último borrador público del Comité del 12 de abril de 2011" (PDF) . pág. 346 y siguientes . Consultado el 21 de diciembre de 2014 . 
  22. ↑ Dohmann, Birgit; Falk, Michael; Lessenich, Karin (agosto de 1991). "Los generadores de números aleatorios de la familia Turbo Pascal". Computational Statistics & Data Analysis . 12 (1): 129– 132. doi : 10.1016/0167-9473(91)90108-E .
  23. ↑ "Cómo Visual Basic genera números pseudoaleatorios para la función RND" . Microsoft. 24 de junio de 2004. Archivado del original el 17 de abril de 2011. Consultado el 17 de junio de 2011 .
  24. ↑ A pesar de la documentación en MSDN , RtlUniform utiliza LCG y no el algoritmo de Lehmer; las implementaciones anteriores a Windows Vista son defectuosas, porque el resultado de la multiplicación se reduce a 32 bits antes de aplicar el módulo.
  25. ↑ "Búsqueda del identificador de origen WINE: RtlUniform" . Consultado el 13 de enero de 2024 .
  26. 1 2 "ISO/IEC 14882:2011" . ISO. 2 de septiembre de 2011. Consultado el 3 de septiembre de 2011 .
  27. ↑ "Creación y control de una secuencia de números aleatorios" . MathWorks . Consultado el 7 de junio de 2021 .
  28. ↑ "El suplemento MMIX de El arte de la programación informática" . mmix.cs.hm.edu . Consultado el 10 de febrero de 2026 .
  29. ↑ " , — números pseudoaleatorios" . Repositorio git de Newlib . Consultado el 13 de enero de 2024 .randsrand
  30. ↑ "Biblioteca científica GNU: gsl_rng_vax" .
  31. ↑ Especificaciones básicas de The Open Group, número 7, IEEE Std 1003.1, edición de 2013
  32. ↑ Stephen J. Chapman. "Ejemplo 6.4 – Generador de números aleatorios". "Programación en MATLAB para ingenieros" . 2015. págs. 253–256.
  33. ↑ Stephen J. Chapman. "Ejemplo 6.4 – Generador de números aleatorios". "Programación en MATLAB con aplicaciones para ingenieros" . 2012. págs. 292–295.
  34. ↑ SJ Chapman. random0 . 2004.
  35. ↑ Stephen J. Chapman. "Introducción a Fortran 90/95" . 1998. págs. 322–324.
  36. ↑ Wu-ting Tsai. "'Módulo': una característica importante del Fortran moderno". Archivado el 24 de febrero de 2021 en Wayback Machine . págs. 6-7.
  37. ↑ Cadot, Sidney. "rand.s" . cc65 . Consultado el 8 de julio de 2016 .
  38. ↑ Cadot, Sidney. "rand.s" . cc65 . Consultado el 10 de marzo de 2025 .
  39. ↑ O'Neill, Melissa E. (5 de septiembre de 2014). PCG: Una familia de algoritmos simples, rápidos, eficientes en espacio y estadísticamente buenos para la generación de números aleatorios (PDF) (Informe técnico). Harvey Mudd College . págs. 6–7 . HMC-CS-2014-0905. 
  40. ↑ Heath, David; Sanchez, Paul (junio de 1986). "Sobre la adecuación de los generadores de números pseudoaleatorios (o: ¿Qué período tan grande necesitamos?)" . Operations Research Letters . 5 (1): 3– 6. doi : 10.1016/0167-6377(86)90092-1 .
  41. ↑ Tezuka, Shu; L'Ecuyer, Pierre (octubre de 1993). Sobre la estructura reticular de los generadores de números aleatorios de suma con acarreo y resta con préstamo (PDF) . Taller sobre métodos numéricos estocásticos. Universidad de Kioto.
  42. ↑ Tezuka, Shi; L'Ecuyer, Pierre (diciembre de 1992). Análisis de generadores de suma con acarreo y resta con préstamo (PDF) . Actas de la Conferencia de Simulación de Invierno de 1992. págs. 443–447 . 
  43. ↑ Gershenfeld , Neil (1999). «Sección 5.3.2: Retroalimentación lineal». La naturaleza del modelado matemático (Primera ed.). Cambridge University Press. pág. 59. ISBN   978-0-521-57095-4.
  44. ↑ Matsumoto, Makoto; Nishimura, Takuji (enero de 1998). "Mersenne twister: un generador de números pseudoaleatorios uniformes equidistribuidos de 623 dimensiones" (PDF) . ACM Transactions on Modeling and Computer Simulation . 8 (1): 3–30 . CiteSeerX 10.1.1.215.1141 . doi : 10.1145/272991.272995 . S2CID 3332028. Archivado del original (PDF) el 7 de noviembre de 2017.  
  45. ↑ Eastlake, Donald E. 3rd; Schiller, Jeffrey I.; Crocker, Steve (junio de 2005). "Secuencias pseudoaleatorias tradicionales" . Requisitos de aleatoriedad para la seguridad . IETF . sec. 6.1.3. doi : 10.17487/RFC4086 . BCP 106. RFC 4086 . 

Referencias

  • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 7.1.1. Un poco de historia" , Numerical Recipes: The Art of Scientific Computing (3.ª  ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8Archivado del original el 11 de agosto de 2011 , consultado el 10 de agosto de 2011.
  • Gentle, James E., (2003). Generación de números aleatorios y métodos de Monte Carlo , 2.ª edición, Springer, ISBN 0-387-00178-6.
  • Joan Boyar (1989). "Inferencia de secuencias producidas por generadores de números pseudoaleatorios" (PDF) . Journal of the ACM . 36 (1): 129– 141. doi : 10.1145/58562.59305 . S2CID 3565772. Archivado del original (PDF) el 30 de abril de 2013. Consultado el 25 de marzo de 2019 . (En este artículo se presentan algoritmos eficientes para inferir secuencias producidas por ciertos generadores de números pseudoaleatorios).
  • La simulación Generador Congruencial Lineal visualiza las correlaciones entre los números pseudoaleatorios al manipular los parámetros.
  • Seguridad en la generación de números aleatorios: una bibliografía comentada.
  • Generadores congruenciales lineales publicados en sci.math
  • El proyecto de arte digital "La muerte del arte" de Goldstein Technologies LLC utiliza un generador de gráficos por computadora (LCG) para generar 33.554.432 imágenes.
  • P. L'Ecuyer y R. Simard, "TestU01: Biblioteca AC para pruebas empíricas de generadores de números aleatorios" , mayo de 2006, revisado en noviembre de 2006, ACM Transactions on Mathematical Software , 33, 4, Artículo 22, agosto de 2007.
  • Artículo sobre otra forma de resolver LCG
Obtenido de " https://en.wikipedia.org/w/index.php?title=Linear_congruential_generator&oldid=1358008465 "
Lecturas relacionadas
6 articulos
AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...Función lineal por partesFunción lineal por partesEn matemáticas , una función lineal por partes o segmentada es una función de valor real de una variable real, cuyo gráfico está compuesto por segm...{\estilo de visualización P}Generador de números pseudoaleatoriosUn generador de números pseudoaleatorios ( PRNG ), también conocido como generador de bits aleatorios determinista ( DRBG ), [1] es un algoritmo pa...Aritmética modularAritmética modularEn matemáticas , la aritmética modular es un sistema de aritmética para números enteros , en el que los números se "enrollan" al alcanzar un valor ...{\estilo de visualización n}Relación de recurrenciaEn matemáticas , una relación de recurrencia es una ecuación según la cual el término n de una secuencia de números es igual a alguna combinación d...SecuenciaUna secuencia infinita de números reales (en azul). Esta secuencia no es ni creciente ni decreciente, ni convergente ni de Cauchy . Sin embargo, es...