stringtranslate.com

Generador lineal congruencial

Dos LCG de módulo 9 muestran cómo diferentes parámetros conducen a diferentes duraciones 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. Usar a  = 4 y c  = 1 (fila inferior) da una longitud de ciclo de 9 con cualquier semilla en [0, 8].

Un generador lineal congruencial ( 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 fácilmente y son rápidos, 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 :

donde es la secuencia de valores pseudoaleatorios, y

— el " módulo "
— el "multiplicador"
— el "incremento"
— 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 llama 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 nombre inapropiado 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 elección adecuada de los 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. [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 my a . [1] [2] [7] [8] [9] [10] Por ejemplo, a  = 1 yc = 1 produce un contador módulo- m  simple , que tiene un período largo, pero obviamente no es aleatorio. Otros valores de c coprimo a m producen una secuencia de Weyl , que está mejor distribuida pero obviamente aún no es aleatoria.

Históricamente, las malas decisiones han conducido a implementaciones ineficaces de las LCG. Un ejemplo particularmente ilustrativo de esto es RANDU , que fue ampliamente utilizado a principios de la década de 1970 y condujo a muchos resultados que actualmente están siendo cuestionados debido al uso de este pobre LCG. [11] [8] : 1198–9 

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

metroprincipal,C= 0

Esta es la construcción original de Lehmer RNG. El período es m −1 si se elige el multiplicador a como elemento primitivo de los números 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 justo 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  ⌊ hacha /2 mi ⌋ . 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 puede limitarse fácilmente a uno si d es pequeño.

Si no se dispone de un producto de doble ancho y el multiplicador se elige con cuidado, se puede utilizar el método de Schrage [12] . Para hacer esto, factorice m  =  qa + r , es decir q = ⌊ m / a ⌋ y r = m mod a . Luego calcula 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 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 único, y la diferencia entre ellos se encuentra en el rango [1− m ,  m −1], por lo que se puede reducir a [0,  m −1] con una única suma condicional . [13]

Una segunda desventaja es que resulta complicado convertir el valor 1 ≤  x  <  m en 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.

metrouna potencia de 2,C= 0

Elegir m como una potencia de dos , generalmente m = 2 32 o m = 2 64 , produce un LCG particularmente eficiente, porque esto 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. Sin embargo, existen desventajas.

Esta forma tiene período máximo m /4, que se logra si a  ≡ ±3 (mod 8) y el estado inicial X 0 es impar. Incluso en el mejor de los casos, los tres bits inferiores de X alternan entre dos valores y, por tanto, sólo contribuyen con un bit al estado. X siempre es impar (el bit de orden más bajo nunca cambia) y sólo 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 yc ≠ 0. [1]

Un problema más grave 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. Su simplicidad de implementación proviene del hecho de que los bits nunca se ven afectados por bits de orden superior, por lo que los bits b bajos de dicho generador forman un LCG módulo-2 b por sí mismos, repitiéndose con un período de 2 b −2 . Sólo el bit más significativo de X alcanza el período completo.

metrouna 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 semillas. Esto ocurrirá si y sólo si : [1] : 17–19 

  1. y son coprimos,
  2. es divisible por todos los factores primos de ,
  3. es divisible por 4 si es divisible por 4.

Estos tres requisitos se conocen como teorema de Hull-Dobell. [14] [15]

Esta forma se puede utilizar con cualquier m , pero sólo 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 entero sin cuadrados , esto solo permitiría a  ≡ 1 (mod  m ), lo que genera un PRNG muy pobre; una selección de posibles multiplicadores de período completo sólo 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 más divisible por factores primos de m de lo necesario. Si m es una potencia de 2, entonces a  − 1 debería ser divisible por 4 pero no divisible 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 pasa una prueba de no aleatoriedad u otra, y encontrar un multiplicador que sea satisfactorio para todos los criterios aplicables [1] : §3.3.3  es todo un desafío. [8] La prueba espectral es una de las pruebas más importantes. [dieciséis]

Tenga en cuenta que un módulo de potencia de 2 comparte el problema descrito anteriormente para c  = 0: los k bits bajos forman un generador con módulo 2 k y, por lo tanto, se repiten con un período de 2 k ; sólo la parte más significativa 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 ( X % r), por lo que se usa con mucha frecuencia.

El generador no es sensible a la elección de c , siempre que sea relativamente primo con respecto 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 secuencia producida por otras elecciones de c se puede escribir 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 e Y n +1 =  aY n + 1 mod m, entonces se puede escribir  una secuencia general X n +1 =  aX n  +  c mod  m como función afín de Y :

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

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 de modo 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 cierto para todos los 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 e Y n +1 = 157 Y n  + 1 mod 256; es decir, m  = 256, a  = 157 y c  = 3. Como 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:

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 deficientes. Hay disponibles tablas de buenos parámetros. [10] [2]

Como se muestra arriba, los LCG no siempre utilizan todos los bits en los valores que producen. En general, devuelven los bits más significativos. Por ejemplo, la implementación de Java opera con valores de 48 bits en cada iteración pero devuelve sólo 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 aquellos que no la utilizan. Esto es especialmente notable en scripts que utilizan la operación mod para reducir el alcance; modificar el número aleatorio mod 2 conducirá a la alternancia de 0 y 1 sin truncamiento.

Por el contrario, algunas bibliotecas utilizan un módulo de potencia de dos implícito pero nunca generan ni utilizan el bit más significativo, para 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 la palabra interna, y dichos generadores se describen como tales en la tabla anterior.

Ventajas y desventajas

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

Hiperplanos de un generador congruencial lineal en tres dimensiones. Esta estructura es lo 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 la gente haya sido adormecida durante tantos años para utilizarlos con módulos tan pequeños puede verse como un testimonio de la solidez de la técnica. Un LCG con un estado suficientemente grande puede pasar incluso pruebas estadísticas rigurosas; un LCG módulo 2 64 que devuelve los 32 bits altos pasa la suite SmallCrush de TestU01 , [ cita necesaria ] y un LCG de 96 bits pasa la suite BigCrush más estricta. [35]

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 cumpleaños ) comience a duplicar salidas anteriores después de √ m ≈ 2 16 resultados. Cualquier PRNG cuya salida 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 debería tener un período más largo que el cuadrado del número de resultados requeridos. Dadas las velocidades de las computadoras modernas, esto significa un período de 2,64 para todas las aplicaciones excepto las menos exigentes, y más largo para las simulaciones exigentes.

Un defecto específico de los LCG es que, si se usan para elegir puntos en un espacio n-dimensional, los puntos se ubicarán, 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 normalmente tendrán muchos menos planos y estarán muy espaciados, lo que puede generar problemas. La prueba espectral , que es una prueba sencilla de la calidad de un LCG, mide esta separación y permite elegir un buen multiplicador.

La separación 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 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 desde un punto de vista puramente probabilístico resulta extremadamente improbable encontrar un multiplicador malo cuando el módulo es mayor que aproximadamente 2 64 .

Otro defecto específico de los LCG es el corto período 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 utilizando 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 ser muy limitada. De manera similar, en un entorno como el de una consola de videojuegos, puede ser suficiente tomar un pequeño número de bits de alto orden de un LCG. (Nunca se debe confiar en los bits de orden inferior de los LCG cuando m es una potencia de 2 para ningún grado de aleatoriedad). Los bits de orden inferior pasan por ciclos muy cortos. En particular, cualquier LCG de ciclo completo, cuando m es una potencia de 2, producirá resultados pares e impares alternativamente.

Los LCG deben evaluarse con mucho cuidado 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 que se requieren. Esto significa, por ejemplo, que se puede utilizar un (buen) LCG de 32 bits para obtener alrededor de mil números aleatorios; un LCG de 64 bits es bueno para aproximadamente 221 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 Monte Carlo a gran escala.

Código de muestra

código pitón

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

de  collections.abc  generador de importación def  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 de rendimiento de semilla

Pascal libre

Free Pascal usa un Mersenne Twister como 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}{$modo delphi}{$endif} interfaz función LCGRandom : extendida ; sobrecarga ; en línea ; función LCGRandom ( rango constante : entero largo ) : entero largo ; sobrecarga ; en línea ;         función de implementación IM : cardinal ; en línea ; comenzar RandSeed : = RandSeed * 134775813 + 1 ; Resultado : = RandSeed ; fin ;             función LCGRandom : extendida ; sobrecarga ; en línea ; comenzar resultado : = IM * 2.32830643653870e-10 ; fin ;         función LCGRandom ( rango constante : entero largo ) : entero largo ; sobrecarga ; en línea ; comenzar Resultado : = IM * rango shr 32 ; fin ;

Como todos los generadores de números pseudoaleatorios, un LCG necesita almacenar el estado y modificarlo cada vez que genera un nuevo número. Varios subprocesos pueden acceder a este estado simultáneamente provocando una condición de carrera. Las implementaciones deben usar estados diferentes, 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 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 LCG.

Un método para producir un período más largo es sumar las producciones 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 solo LCG con un módulo igual al producto de los módulos LCG del componente.

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

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 congruente permutado comienza con un LCG de potencia de 2 módulos 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 polinómico sobre GF(2) . En lugar de la suma y multiplicación de números enteros, las operaciones básicas son la multiplicación exclusiva o 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 . [38]

Ejemplos de esta familia incluyen los generadores xorshift y el tornado Mersenne . Este último proporciona un período muy largo (2 19937 −1) y uniformidad variable, pero no supera algunas pruebas estadísticas. [39] Los generadores rezagados de Fibonacci también entran en esta categoría; aunque utilizan 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 pruebas apropiadas [40], 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 generador congruencial permutadas ) 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 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 poderosa para generar números pseudoaleatorios de alta calidad es combinar dos o más PRNG de diferente estructura; la suma de LFSR y LCG (como en las construcciones KISS o xorwow ) puede funcionar muy bien con cierto costo en velocidad.

Ver también

Notas

  1. ^ abcdefg Knuth, Donald (1997). Algoritmos Seminuméricos . El arte de la programación informática . vol. 2 (3ª ed.). Reading, MA: Addison-Wesley Profesional. págs. 10–26.
  2. ^ abcd 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 congruentes" (PDF) . Software: práctica y experiencia . 52 (2): 443–458. arXiv : 2001.05304 . doi : 10.1002/spe.3030 . estas denominaciones, que ya se utilizan desde hace medio siglo, son completamente erróneas desde un punto de vista matemático... A estas alturas es poco probable que los nombres ahora tradicionales sean corregidos.Software y datos asociados en https://github.com/vigna/CPRNG.
  3. ^ Lehmer, Derrick H. (1951). "Métodos matemáticos en unidades informáticas de gran escala". Actas del segundo simposio sobre maquinaria de cálculo digital a gran escala : 141–146.
  4. ^ Thomson, NOSOTROS (1958). "Un método de congruencia modificado para generar números pseudoaleatorios". La revista informática . 1 (2): 83. doi : 10.1093/comjnl/1.2.83 .
  5. ^ Rothenberg, A. (1960). "Un nuevo generador de números pseudoaleatorios". Revista de la 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.; Página, E. (eds.). Historia de la generación uniforme de números aleatorios (PDF) . Actas de la Conferencia de simulación de invierno de 2017 (aparecer). Las Vegas, Estados Unidos. hal-01561551.
  7. ^ ab Marsaglia, George (septiembre de 1968). "Los números aleatorios caen principalmente en los aviones" (PDF) . PNAS . 61 (1): 25–28. Código bibliográfico : 1968PNAS...61...25M. doi : 10.1073/pnas.61.1.25 . PMC 285899 . PMID  16591687. 
  8. ^ Parque abcd, Stephen K.; Miller, Keith W. (octubre de 1988). "Generadores de números aleatorios: los buenos son difíciles de encontrar" (PDF) . Comunicaciones de la ACM . 31 (10): 1192-1201. doi :10.1145/63039.63042. S2CID  207575300. En cierto sentido, es lamentable que esta prueba de 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 uniforme muy adecuado para el método de rechazo" (PDF) . Transacciones ACM sobre software matemático . 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. ^ ab L'Ecuyer, Pierre (enero de 1999). "Tablas de Generadores Lineales Congruenciales de Diferentes Tamaños y Buena Estructura Reticular" (PDF) . Matemáticas de la Computación . 68 (225): 249–260. Código Bib : 1999MaCom..68..249L. CiteSeerX 10.1.1.34.1024 . doi :10.1090/S0025-5718-99-00996-5.  Asegúrese de leer también la fe de erratas.
  11. ^ ab Prensa, William H.; et al. (1992). Recetas numéricas en Fortran 77: el arte de la informática científica (2ª ed.). pag. 268.ISBN​ 978-0-521-43064-7.
  12. ^ Jain, Raj (9 de julio de 2010). "Capítulo 26 del análisis del rendimiento de los sistemas informáticos: generación de números aleatorios" (PDF) . págs. 19-20 . Consultado el 31 de octubre de 2017 .
  13. ^ Fenerty, Paul (11 de septiembre de 2006). "El método de Schrage" . Consultado el 31 de octubre de 2017 .
  14. ^ Casco, TE; Dobell, AR (julio de 1962). "Generadores de números aleatorios" (PDF) . Revisión SIAM . 4 (3): 230–254. Código Bib : 1962SIAMR...4..230H. doi :10.1137/1004061. hdl : 1828/3142 . Consultado el 26 de junio de 2016 .
  15. ^ Indemnización, Frank (2001). Modelado y Simulación de Sistemas . John Wiley & Sons, Ltd. pág. 86.ISBN​ 978-0-471-49694-6.
  16. ^ Austin, David (marzo de 2008). "Números aleatorios: nada dejado al azar". Columna de características . Sociedad Matemática Estadounidense.
  17. ^ Implementación en la versión glibc-2.26. Vea el código después de la prueba para "TYPE_0"; rand() de la biblioteca GNU C en stdlib.h utiliza un generador congruencial lineal simple (estado único) solo en caso de que el estado se declare como 8 bytes. Si el estado es más grande (una matriz), el generador se convierte en un generador de retroalimentación aditiva (inicializado usando minstd_rand0) y el período aumenta. Vea el código simplificado que reproduce la secuencia aleatoria de esta biblioteca.
  18. ^ 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 . Consultado el 16 de junio de 2012 . 
  19. ^ "Último borrador público del Comité del 12 de abril de 2011" (PDF) . pag. 346 y siguientes . Consultado el 21 de diciembre de 2014 .
  20. ^ Dohmann, Birgit; Falk, Michael; Lessenich, Karin (agosto de 1991). "Los generadores de números aleatorios de la familia Turbo Pascal". Estadística computacional y análisis de datos . 12 (1): 129-132. doi :10.1016/0167-9473(91)90108-E.
  21. ^ "Cómo Visual Basic genera números pseudoaleatorios para la función RND". Microsoft. 24 de junio de 2004. Archivado desde el original el 17 de abril de 2011 . Consultado el 17 de junio de 2011 .
  22. ^ A pesar de la documentación en MSDN, RtlUniform usa LCG, y no el algoritmo de Lehmer, las implementaciones anteriores a Windows Vista son defectuosas, porque el resultado de la multiplicación se corta a 32 bits, antes de aplicar el módulo.
  23. ^ "Búsqueda de identificador de fuente WINE: RtlUniform" . Consultado el 13 de enero de 2024 .
  24. ^ ab "ISO/IEC 14882:2011". YO ASI. 2 de septiembre de 2011 . Consultado el 3 de septiembre de 2011 .
  25. ^ "Creación y control de una secuencia de números aleatorios". Trabajos de matemáticas . Consultado el 7 de junio de 2021 .
  26. ^ "rand, srand: números pseudoaleatorios". Repositorio git de Newlib . Consultado el 13 de enero de 2024 .
  27. ^ "Biblioteca científica GNU: gsl_rng_vax".
  28. ^ Stephen J. Chapman. "Ejemplo 6.4: Generador de números aleatorios". "Programación MATLAB para ingenieros". 2015, págs. 253–256.
  29. ^ Stephen J. Chapman. "Ejemplo 6.4: Generador de números aleatorios". "Programación MATLAB con Aplicaciones para Ingenieros". 2012, págs. 292–295.
  30. ^ SJ Chapman. aleatorio0. 2004.
  31. ^ Stephen J. Chapman. "Introducción a Fortran 90/95". 1998, págs. 322–324.
  32. ^ 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.
  33. ^ Especificaciones básicas de Open Group Edición 7 IEEE Std 1003.1, edición 2013
  34. ^ Cadot, Sidney. "rand.s". cc65 . Consultado el 8 de julio de 2016 .
  35. ^ O'Neill, Melissa E. (5 de septiembre de 2014). PCG: una familia de algoritmos estadísticamente buenos, simples, rápidos y eficientes en el espacio para la generación de números aleatorios (PDF) (Reporte técnico). Universidad Harvey Mudd . págs. 6–7. HMC-CS-2014-0905.
  36. ^ 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 de Numéricas Estocásticas. Universidad de Kioto.
  37. ^ 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.
  38. ^ Gershenfeld, Neil (1999). "Sección 5.3.2: Retroalimentación lineal". La naturaleza del modelado matemático (Primera ed.). Prensa de la Universidad de Cambridge. pag. 59.ISBN​ 978-0-521-57095-4.
  39. ^ Matsumoto, Makoto; Nishimura, Takuji (enero de 1998). "Mersenne Twister: un generador de números pseudoaleatorios uniformes equidistribuidos de 623 dimensiones" (PDF) . Transacciones ACM sobre modelado y simulación por computadora . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . doi :10.1145/272991.272995. S2CID  3332028. Archivado desde el original (PDF) el 7 de noviembre de 2017. 
  40. ^ Eastlake, Donald E. tercero; Schiller, Jeffrey I.; Crocker, Steve (junio de 2005). "Secuencias pseudoaleatorias tradicionales". Requisitos de aleatoriedad para la seguridad. IETF . segundo. 6.1.3. doi : 10.17487/RFC4086 . BCP 106. RFC 4086.

Referencias

enlaces externos