stringtranslate.com

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 que evoluciona 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. El uso de a  = 4 y c  = 1 (fila inferior) da 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 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 de manera fácil y rápida, especialmente en hardware de computadora que puede proporcionar aritmética modular mediante el truncamiento de bits de almacenamiento.

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

¿Dónde está 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 se denomina a menudo generador congruencial multiplicativo (MCG) o generador aleatorio 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 nombre erróneo está bien establecido en la ciencia 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 que es 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 m y a . [1] [2] [7] [8] [9] [10] Por ejemplo, a  = 1 y c  = 1 produce un contador módulo m simple , que tiene un período largo, pero obviamente no aleatorio. Otros valores de c coprimos con m producen una secuencia de Weyl , que está mejor distribuida pero obviamente aún no aleatoria.

Históricamente, las malas decisiones sobre a han llevado a implementaciones ineficaces de LCG. Un ejemplo particularmente ilustrativo de esto es RANDU , que se utilizó ampliamente a principios de la década de 1970 y condujo a muchos resultados que actualmente se cuestionan debido al uso de este LCG deficiente. [11] [8] : 1198–9 

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

metroprincipal,do= 0

Esta es la construcción original del generador de números aleatorios de Lehmer. El período es m −1 si se elige que el multiplicador a sea un 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  ⌊ ax /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 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 ello, se factoriza m  =  qa + r , es decir, q = ⌊ m / a ⌋ y r = m mod a . Luego se 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 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 único, 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 única suma condicional. [13]

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

metrouna potencia de 2,do= 0

Si se elige m como potencia de dos , generalmente m = 2 32 o m = 2 64 , se obtiene un LCG particularmente eficiente, ya que esto permite calcular la operación de 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 un periodo máximo m /4, que se logra si a  ≡ ±3 (mod 8) y el estado inicial X 0 es impar. Incluso en este mejor caso, los tres bits más bajos de X alternan entre dos valores y, por lo tanto, solo contribuyen con un bit al estado. X siempre es impar (el bit de orden más bajo 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 (todos 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 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 un generador de este tipo forman un LCG módulo 2 b por sí mismos, repitiéndose con un período de 2 b −2 . Solo el bit más significativo de X alcanza el período completo.

metrouna potencia de 2,do≠ 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. 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 el Teorema de Hull-Dobell. [14] [15]

Esta forma se puede utilizar 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 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 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 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 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 u otra prueba de no aleatoriedad, 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. [16]

Nótese que un módulo de potencia de 2 comparte el problema descrito anteriormente para c  = 0: los bits k bajos forman un generador con módulo 2 k y, por lo tanto, se repiten con un período de 2 k ; solo el bit más significativo logra 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 muy comúnmente.

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 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 una secuencia general X n +1 =  aX n  +  c mod  m se puede escribir como una 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 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 verdadera 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 simple, considere 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), así que si empezamos con eso, entonces X n ≡  X 0  −  Y n  (mod 256) para todo n .

Por ejemplo, utilizando 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 ejecución de varios compiladores . Esta tabla es para mostrar la popularidad, no para dar ejemplos; 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 solo sus 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 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 rango; modificar el número aleatorio mod 2 dará lugar 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 o utilizan de otro modo el bit más significativo, con el fin de limitar la salida a números 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 generadores de números aleatorios (LCG) son rápidos y requieren una cantidad mínima de memoria (un número módulo m , a menudo 32 o 64 bits) para retener el estado. Esto los hace valiosos para simular múltiples flujos independientes. Los LCG no están pensados ​​para aplicaciones criptográficas y no deben utilizarse para ellas; 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 la 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 fortaleza de la técnica. Un LCG con un estado lo suficientemente grande puede pasar incluso pruebas estadísticas rigurosas; un LCG de 64 bits módulo 2 que devuelve los 32 bits más altos pasa la suite SmallCrush de TestU01 , [ cita requerida ] 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 (por el teorema de Birthday ) comience a duplicar salidas anteriores después de √ m ≈ 2 16 resultados. Cualquier PRNG cuya salida sea su estado completo, no truncado, no producirá duplicados hasta que transcurra su período completo, una falla estadística fácilmente detectable. [36] Por razones relacionadas, cualquier PRNG debe tener un período más largo que el cuadrado del número de salidas requeridas. 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 simulaciones exigentes.

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

El espaciado 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 precisión doble. 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í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 bajo cuando se elige que m sea 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 una pequeña cantidad de bits de orden superior de un LCG. (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 bits de orden inferior 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 en las que la aleatoriedad de alta calidad es fundamental. Para las 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 un LCG (bueno) de 32 bits puede utilizarse para obtener alrededor de mil números aleatorios; un LCG de 64 bits es bueno para alrededor de 2 21 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  colecciones.abc  importar  Generadordef  lcg ( módulo :  int ,  a :  int ,  c :  int ,  semilla :  int )  ->  Generador [ int ,  None ,  None ]: """Generador congruencial lineal.""" mientras True : semilla = ( a * semilla + c ) % módulo rendimiento semilla

Pascal libre

Free Pascal utiliza un Mersenne Twister como generador de números pseudoaleatorios predeterminado, mientras que Delphi utiliza un LCG. A continuación, se muestra 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} interfaz función LCGRandom : extendida ; sobrecarga ; en línea ; función LCGRandom ( const range : longint ) : longint ; sobrecarga ; en línea ;         función de implementación IM : cardinal ; en línea ; comienzo RandSeed := RandSeed * 134775813 + 1 ; Resultado := RandSeed ; fin ;             función LCGRandom : extendida ; sobrecarga ; en línea ; comienzo Resultado := IM * 2.32830643653870e-10 ; fin ;         función LCGRandom ( const range : longint ) : longint ; sobrecarga ; en línea ; comienzo Resultado := IM * range shr 32 ; fin ;

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

Derivados de LCG

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

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 al menos 2). Se puede demostrar que esto es equivalente a un solo LCG con un módulo igual al producto de los módulos del LCG 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 rezagos r y s ( r  >  s ) son equivalentes a los LCG con un módulo de b r  ±  b s  ± 1. [37] [38]

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 módulo de potencia de 2 y aplica una transformación de salida para eliminar el problema del período corto en los bits de orden bajo.

Comparación con otros PRNG

La otra primitiva ampliamente utilizada para obtener secuencias pseudoaleatorias de período largo es la construcción de registros de desplazamiento con 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 multiplicación de números enteros, las operaciones básicas son la multiplicación exclusiva-o y sin acarreo , que generalmente se implementa como una secuencia de desplazamientos lógicos . Estos tienen la ventaja de que todos sus bits son de período completo; no sufren la debilidad en los bits de orden inferior que afecta a la aritmética módulo 2 k . [39]

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 variables, pero no supera algunas pruebas estadísticas. [40] 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 pruebas apropiadas [41], 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 las construcciones de generador congruencial permutado y xoshiro256** ) 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 potente función de mezcla de salida. Esto incluye cifrados de bloque 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 un LFSR y un LCG (como en las construcciones KISS o xorwow ) puede funcionar muy bien con cierto sacrificio en velocidad.

Véase 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 Professional. 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 congruenciales". Software: práctica y experiencia . 52 (2): 443–458. arXiv : 2001.05304 . doi : 10.1002/spe.3030 . hdl :2434/891395. Estas denominaciones, que ya se han utilizado durante medio siglo, son completamente erróneas desde un punto de vista matemático.... En este punto, es poco probable 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". 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.; Page, E. (eds.). History of Uniform Random Number Generation (PDF) . Actas de la Conferencia de Simulación de Invierno de 2017 (próximamente). Las Vegas, Estados Unidos. hal-01561551.
  7. ^ ab 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. ^ abcd Park, Stephen K.; Miller, Keith W. (octubre de 1988). "Generadores de números aleatorios: es difícil encontrar los buenos" (PDF) . Communications of the ACM . 31 (10): 1192–1201. doi :10.1145/63039.63042. S2CID  207575300. En cierto sentido, es desafortunado 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 de números aleatorios uniforme portátil 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. ^ ab 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 la sección de erratas.
  11. ^ ab Press, William H.; et al. (1992). Recetas numéricas en Fortran 77: el arte de la computación científica (2.ª ed.). pág. 268. ISBN 978-0-521-43064-7.
  12. ^ Jain, Raj (9 de julio de 2010). «Computer Systems Performance Analysis Chapter 26: Random-Number Generation» (PDF) . pp. 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. ^ Hull, TE; Dobell, AR (julio de 1962). "Random Number Generators" (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 .
  15. ^ Severance, 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 se deja al azar". Columna destacada . 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"; la función rand() de la biblioteca C de GNU en stdlib.h usa un generador congruencial lineal simple (de un solo estado) solo en caso de que el estado se declare como de 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) . p. 346f . 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". Computational Statistics & Data Analysis . 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 utiliza 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 origen de WINE: RtlUniform" . Consultado el 13 de enero de 2024 .
  24. ^ ab "ISO/IEC 14882:2011". ISO. 2 de septiembre de 2011. Consultado el 3 de septiembre de 2011 .
  25. ^ "Creación y control de un flujo de números aleatorios". MathWorks . 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 en MATLAB para ingenieros". 2015. págs. 253-256.
  29. ^ Stephen J. Chapman. "Ejemplo 6.4: generador de números aleatorios". "Programación en 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 . pp. 6–7.
  33. ^ Especificaciones básicas de The Open Group, número 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 simples, rápidos y con uso eficiente del 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.
  36. ^ Heath, David; Sanchez, Paul (junio de 1986). "Sobre la idoneidad de los generadores de números pseudoaleatorios (o: ¿Qué período necesitamos?)". Operations Research Letters . 5 (1): 3–6. doi :10.1016/0167-6377(86)90092-1.
  37. ^ 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 números estocásticos. Universidad de Kioto.
  38. ^ 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.
  39. ^ Gershenfeld, Neil (1999). "Sección 5.3.2: Retroalimentación lineal". La naturaleza del modelado matemático (primera edición). Cambridge University Press. pág. 59. ISBN 978-0-521-57095-4.
  40. ^ Matsumoto, Makoto; Nishimura, Takuji (enero de 1998). "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator" (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 desde el original (PDF) el 2017-11-07. 
  41. ^ Eastlake, Donald E. 3rd; Schiller, Jeffrey I.; Crocker, Steve (junio de 2005). "Secuencias pseudoaleatorias tradicionales". Requisitos de aleatoriedad para seguridad. IETF . sec. 6.1.3. doi : 10.17487/RFC4086 . BCP 106. RFC 4086.

Referencias

Enlaces externos