LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Dos LCG modulo-9 muestran cómo diferentes parámetros conducen a diferentes ciclos de duración. 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. Utilizando a  = 4 y c  = 1 (fila inferior) se obtiene una longitud de ciclo de 9 con cualquier semilla en [0, 8].

Un generador lineal congruente ( LCG ) es un algoritmo que produce una secuencia de números pseudoaleatorios calculados con una ecuación linealdiscontinua por partes . El método representa uno de los algoritmos de generación de números pseudoaleatorios más antiguos y conocidos . ^[1] 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 módulo aritmético mediante el truncamiento de bits de almacenamiento.

El generador se define por relación de recurrencia :

$${\ displaystyle X_ {n + 1} = \ left (aX_ {n} + c \ right) ~~ {\ bmod {~}} ~ m}

dónde $${\ displaystyle X}es la secuencia de valores pseudoaleatorios, y

{\ displaystyle m, \, 0 - el " módulo "

{\ displaystyle a, \, 0  - el "multiplicador"

{\ displaystyle c, \, 0 \ leq c  - el "incremento"

{\ displaystyle X_ {0}, \, 0 \ leq X_ {0}  - la "semilla" o "valor de inicio"

Son constantes enteras que especifican el generador. Si c  = 0, el generador a menudo se llama un generador congruente multiplicativo (MCG), o Lehmer RNG . Si c  ≠ 0, el método se llama un generador congruente mixto.

Longitud del período [ editar ]

Un beneficio de los LCG es que con la elección adecuada de los parámetros, el período 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. ^[3]

Si bien los LCG son capaces de producir números pseudoaleatorios que pueden pasar pruebas formales de aleatoriedad , esto es extremadamente sensible a la elección de los parámetros m y a . ^{[ aclaración necesaria ]} Por ejemplo, a  = 1 y c  = 1 produce un contador de módulo m simple , que tiene un período largo, pero obviamente no es aleatorio.

Históricamente, las malas elecciones para una han llevado a implementaciones ineficaces de GCV. Un ejemplo particularmente ilustrativo de esto es RANDU , que se usó ampliamente a principios de la década de 1970 y dio lugar a muchos resultados que actualmente están siendo cuestionados debido al uso de este deficiente LCG. ^[4]

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

m prime, c = 0 [ editar ]

Esta es la formulación original de Lehmer RNG . El período es m −1 si el multiplicador a es elegido para ser 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 principal es que la reducción modular requiere un producto de doble ancho y un paso de reducción explícito. A menudo, se usa un cebado solo menor que una potencia de 2 (los primos de Mersenne 2 ³¹ −1 y 2 ⁶¹ −1 son populares), de modo que el módulo de reducción 2 ^e  -  d se puede calcular como ( ax  mod 2 ^e ) -  d  ⌊ ax / 2 ^e ⌋. Esto debe ir seguido de una adición condicional de m si el resultado es negativo, pero el número de adiciones se limita a ad / m , que puede limitarse fácilmente a uno si d es pequeño.

Si un producto de doble ancho no está disponible y el multiplicador se elige con cuidado, se puede usar el método de Schrage ^[5] . Para ello, el factor m  =  qa + r , es decir, q = ⌊ m / una ⌋ y r = m mod una . Entonces calcular ax  mod  m = un ( x mod q ) - r  ⌊ x / q ⌋ . Desde x  mod  q < q ≤ m /a , el primer término es estrictamente menor que am / a  =  m . Si una se elige de modo que r  ≤  q (y por tanto r / q  ≤ 1), entonces el segundo término es también: r  ⌊ x / q ⌋ ≤ rx / q = x ( r / q ) ≤ x (1) = x < m . Por lo tanto, ambos productos se pueden calcular con un producto de una sola bruja, y la diferencia entre ellos se encuentra en el rango [1− m ,  m−1], sp se puede reducir a [0,  m −1] con un solo agregado condicional. ^[6]

Una segunda desventaja es que es incómodo convertir el valor 1 ≤  x  <  m en bits aleatorios uniformes. Si se usa un cebado solo menor que una potencia de 2, a veces los valores faltantes simplemente se ignoran.

m una potencia de 2, c = 0 [ editar ]

Elegir que m sea ​​una potencia de 2 , la mayoría de las veces m = 2 ³² o m = 2 ⁶⁴ , produce una LCG particularmente eficiente, porque esto permite que la operación de módulo se calcule simplemente truncando la representación binaria. De hecho, los bits más significativos generalmente no se computan en absoluto. Hay, sin embargo, desventajas.

Esta forma tiene un período máximo m / 4, alcanzado si a  ≡ 3 o a  ≡ 5 (mod 8). El estado inicial X ₀ debe ser impar, y los tres bits bajos de X se alternan entre dos estados y no son útiles. Se puede demostrar que esta forma es equivalente a un generador con un módulo de un cuarto del tamaño y c ≠ 0. ^[2]

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. El bit de orden más bajo de X nunca cambia ( X siempre es impar), y los dos bits siguientes se alternan entre dos estados. (Si a  ≡ 5 (mod 8), el bit 1 nunca cambia y el bit 2 se alterna. Si a  ≡ 3 (mod 8), el bit 2 nunca cambia y el bit 1 se alterna.) El bit 3 se repite con un período de 4, bit 4 tiene un período de 8, y así sucesivamente. Sólo el bit más significativo de X logra el período completo.

c ≠ 0 [ editar ]

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

1. $${\ displaystyle \, m} y el desplazamiento $${\ displaystyle \, c}son relativamente primos ,
2. $${\ displaystyle \, a-1}Es divisible por todos los factores primos de$${\ displaystyle \, m},
3. $${\ displaystyle \, a-1} es divisible por 4 si $${\ displaystyle \, m} Es divisible por 4.

Estos tres requisitos se conocen como Teorema de Hull-Dobell. ^[7] [8]

Este formulario puede ser utilizado con cualquier m . Un módulo de potencia de 2 igual al tamaño de palabra deuna computadora es conveniente y alcanza el período más largo posible (para cualquier c y un  mod 1 mod 4), pero tiene el mismo problema mencionado anteriormente: solo el bit más significativo logra el máximo período. El bit de orden inferior k se repite con un período de longitud 2 ^k +1 .

Un módulo impar (generalmente primo) evita este problema, pero como se mencionó anteriormente no puede producir ciertos valores.

Aunque los requisitos anteriores brindan un período máximo, no son suficientes para garantizar un buengenerador. Por ejemplo, es deseable que un −1 no sea más divisible por factores primos de m que lo necesario. Por lo tanto, si m es una potencia de 2, entonces un −1 debería ser divisible por 4 pero no divisible por 8, es decir, un  ≡ 5 (mod 8). ^{[2] : §3.2.1.3} De hecho, la mayoría de los multiplicadores de un producen una secuencia que falla una prueba para no aleatoriedad o de otra, y la búsqueda de un multiplicador que sea satisfactoria para todos los criterios aplicables ^{[2] : §3.3.3} es bastante difícil.

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 el valor c = 1 se elige comúnmente.

La serie producida por otras opciones de c puede escribirse como una función simple de la serie cuando c = 1. ^[2] : 11 Específicamente, si Y es la serie prototípica definida por Y ₀ = 0 e Y _n +1 =  aY _n +1 mod m, entonces se puede escribir una serie general X _n +1 =  aX _n + c mod  m como una función afín de Y :

$${\ displaystyle X_ {n} = (X_ {0} (a-1) + c) Y_ {n} + X_ {0} = (X_ {1} -X_ {0}) Y_ {n} + X_ {0 } {\ pmod {m}}.}

Más generalmente, cualquiera de las dos series X y Z con el mismo multiplicador y módulo están relacionadas por

$${\ displaystyle {X_ {n} -X_ {0} \ sobre X_ {1} -X_ {0}} = Y_ {n} = {a ^ {n} -1 \ sobre a-1} = {Z_ {n } -Z_ {0} \ sobre Z_ {1} -Z_ {0}} {\ pmod {m}}.}

Parámetros de uso común [ editar ]

La siguiente tabla enumera los parámetros de los LCG de uso común, incluidas las funciones rand ()incorporadas en las bibliotecas de tiempo de ejecución de varios compiladores .

Fuente	módulo m	multiplicador  a	incremento  c	bits de salida de semillas en rand () oaleatorio (L)
Recetas Numéricas	2³²	1664525	1013904223
Borland C / C ++	2³²	22695477	1	bits 30..16 enrand () , 30..0 enlrand ()
glibc (usado por GCC ) [9]	2³¹	1103515245	12345	bits 30..0
ANSI C : Watcom , Digital Mars ,CodeWarrior , IBM VisualAge C / C ++[10] C90 , C99 , C11 : Sugerencia en la norma ISO / IEC 9899 [11] , C18	2³¹	1103515245	12345	bits 30..16
Borland Delphi , Pascal Virtual	2³²	134775813	1	bits 63..32 de(semilla * L)
Turbo Pascal	2³²	134775813 (0x8088405₁₆)	1
Microsoft Visual / Quick C / C ++	2³²	214013 (343FD₁₆)	2531011 (269EC3₁₆)	bits 30..16
Microsoft Visual Basic (6 y anteriores)[12]	2²⁴	1140671485 (43FD43FD₁₆)	12820163 (C39EC3₁₆)
RtlUniform de API nativa [13]	2³¹ - 1	2147483629 (7FFFFFED₁₆)	2147483587 (7FFFFFC3₁₆)
Apple CarbonLib , C ++ 11 'sminstd_rand0[14]	2³¹ - 1	16807	0	verMINSTD
C ++ 11 's minstd_rand[14]	2³¹ - 1	48271	0	verMINSTD
MMIX de Donald Knuth	2⁶⁴	6364136223846793005	1442695040888963407
Newlib , MUSL	2⁶⁴	6364136223846793005	1	bits 63 ... 32
VMS 's MTH $ RANDOM , [15]versiones anteriores de glibc	2³²	69069 (10DCD₁₆)	1
Java 's java.util.Random, POSIX [ln] rand48, glibc [ln] rand48 [_r]	2⁴⁸	25214903917 (5DEECE66D₁₆)	11	bits 47 ... 16
random0[16] [17] [18] [19] [20] Si Xₙ es par, entonces Xₙ od será impar, y viceversa, el bit más bajo oscila en cada paso.	134456 = 2³7⁵	8121	28411	$${\ displaystyle {\ frac {X_ {n}} {134456}}}
POSIX [21] [jm] rand48, glibc [mj] rand48 [_r]	2⁴⁸	25214903917 (5DEECE66D₁₆)	11	bits 47 ... 15
POSIX [de] rand48, glibc [de] rand48 [_r]	2⁴⁸	25214903917 (5DEECE66D₁₆)	11	bits 47 ... 0
cc65 [22]	2²³	65793 (10101₁₆)	4282663 (415927₁₆)	bits 22 ... 8
cc65	2³²	16843009 (1010101₁₆)	826366247 (31415927₁₆)	bits 31 ... 16
Anteriormente común: RANDU [4]	2³¹	65539	0

Como se muestra arriba, los LCG no siempre usan todos los bits en los valores que producen. 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 más abajo). Los LCG que utilizan esta técnica de truncamiento producen valores estadísticamente mejores que aquellos que no lo hacen. Esto es especialmente notable en los scripts que utilizan la operación de modificación para reducir el rango; La modificación del número aleatorio mod 2 llevará a alternar 0 y 1 sin truncamiento.

Ventajas y desventajas [ editar ]

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material sin fuente puede ser cuestionado y eliminado . ( Junio ​​de 2017 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

GLCs son rápidos y requiere mínimo de memoria (una modulo- m número, a menudo 32 o 64 bits) para retener el estado. Esto los hace valiosos para simular múltiples flujos independientes.

Hiperplanos de un generador lineal congruente 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 las personas se hayan calmado durante tantos años para usarlas con módulos tan pequeños puede verse como un testimonio de la fuerza de la técnica. Un LCG con un estado suficientemente grande puede pasar incluso pruebas estadísticas rigurosas; un LCG módulo-2 que devuelve los altos 32 bits pasa TestU01 suite 's SmallCrush, ^{[ citación necesaria ]} y un 96-bit LCG pasa la suite BigCrush más estrictas. ^[23]

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 ¹⁶ 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. 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 modernas de las computadoras, esto significa un período de 2 ⁶⁴ para todas las aplicaciones excepto las menos exigentes y más prolongadas para las simulaciones más exigentes.

Un defecto específico de las LCG es que, si se usan para elegir puntos en un espacio n-dimensional, los puntos se ubicarán, como máximo, en los hiperplanos n √ n ! ⋅ m ( Teorema de Marsaglia , desarrollado por George Marsaglia ). ^[24] Esto se debe a la correlación en serie entre valores sucesivos de la secuencia X _n . Los multiplicadores elegidos sin cuidado por lo general tendrán muchos menos aviones ampliamente espaciados, lo que puede llevar a 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 del plano 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 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 es muy probable que sea extremadamente improbable que encuentre un multiplicador malo cuando el módulo es mayor que aproximadamente 2 ⁶⁴ .

Otra falla específica de las LCG es el corto período de los bits de orden inferior cuando m se elige para ser una potencia de 2. Esto se puede mitigar utilizando un módulo más grande que la salida requerida y utilizando los bits más significativos del estado.

Las LCG deben elegirse con mucho cuidado para aplicaciones donde la aleatoriedad de alta calidad es crítica. Cualquier simulación de Monte Carlo debe usar un LCG con un módulo mayor y preferiblemente mucho mayor que la raíz cúbica del número de muestras aleatorias que se requieren. Esto significa, por ejemplo, que un (bueno) LCG de 32 bits se puede usar para obtener alrededor de mil números aleatorios; un LCG de 64 bits es bueno para aproximadamente 2 ²¹ muestras aleatorias, que es un poco más de dos millones, etc. Por esta razón, los LCG no son adecuados en la práctica para simulaciones de Monte Carlo a gran escala.

Los LCG no están destinados, y no deben usarse, para aplicaciones criptográficas; use un generador de números pseudoaleatorios criptográficamente seguro para tales aplicaciones. 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 estar muy limitada. Del mismo modo, en un entorno como una consola de videojuegos,bastará con un pequeño número de bits de orden superior de una LCG. Los bits de orden inferior de las LCG, cuando m es una potencia de 2, nunca deben confiarse en ningún grado de aleatoriedad en absoluto. De hecho, simplemente sustituyendo 2 ⁿporque el término de módulo revela que los bits de orden bajo pasan por ciclos muy cortos. En particular, cualquier LCG de ciclo completo cuando m es una potencia de 2 producirá resultados impares e incluso alternos.

Código Python de muestra [ editar ]

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

def  lcg ( módulo ,  a ,  c ,  semilla ): 
  while  True : 
    seed  =  ( a  *  seed  +  c )  %  módulo 
    produce  semilla

Código Free Pascal de muestra [ editar ]

Free Pascal usa un Mersenne Twister como su generador predeterminado de números pseudoaleatorios, 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} {$ mode delphi} {$ endif} 
interfaz

función  LCGRandom :  extendida ;  sobrecarga ; inline ; 
función  LCGRandom ( rango const  : longint ) : longint ; sobrecarga ; inline ;


Función de  implementación IM : cardinal ; inline ; 
comienza 
 RandSeed  : =  RandSeed  *  134775813  +  1 ; 
 Resultado  : =  RandSeed ; 
terminar ;

función  LCGRandom :  extendida ;  sobrecarga ; inline ; 
comienzo 
 Resultado  : =  IM  *  2.32830643653870e-10 ; 
terminar ;

función  LCGRandom ( rango const  : longint ) : longint ; sobrecarga ; inline ; comienzo Resultado : = IM * rango de shr 32 ; terminar ;

       

Al igual que 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 causando una condición de carrera. Las implementaciones deben usar un estado diferente, 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 de LCG [ editar ]

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

Un método para producir un período más largo es sumar los resultados de varios LCG de diferentes períodos que tienen un gran múltiplo menos común ; la Wichmann-Hill generador es un ejemplo de esta forma. (Preferiríamos que sean completamente de coprimo , pero un módulo principal implica un período parejo, por lo que debe haber un factor común de 2, al menos). Esto puede mostrarse como equivalente a un solo LCG con un módulo igual al Producto del componente LCG moduli.

Los PRNG de Marsaglia para agregar y llevar y restar con préstamo con un tamaño de palabra de b = 2 ^w y retrasos r y s ( r  >  s ) son equivalentes a los LCG con un módulo de b ^r  ±  b ^s  ± 1. ^[25] [26]

Los PRNG de multiplicación con acarreo con un multiplicador de a son equivalentes a los LCG con un módulo principal 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 PRNGs [ editar ]

Generadores basados ​​en recidivas lineales (tales como xorshift *) o en buenas funciones de avalanchas (como SplitMix64 [1] ) superan a los generadores lineales congruentes incluso en tamaños de estados pequeños. Además, los generadores lineales pueden generar secuencias muy largas, y cuando se les perturba adecuadamente en la salida, pasan pruebas estadísticas sólidas. Varios ejemplos se pueden encontrar en la familia Xorshift .

El algoritmo Twister de Mersenne proporciona un período muy largo (2¹⁹⁹³⁷ - 1) y variabilidad uniforme, pero falla algunas pruebas estadísticas. ^[27] Una implementación común de Mersenne twister usa un LCG para generar datos semilla. ^{[ cita requerida ]}

Los generadores lineales congruentes tienen el problema de que todos los bits en cada número generalmente no son igualmente aleatorios. O bien el módulo es una potencia de 2 y los bits menos significativos son menos aleatorios que los bits más significativos, o el módulo no es una potencia de 2 y las salidas están sesgadas. Un registro de desplazamiento de realimentación lineal PRNG produce un flujo de bits pseudoaleatorios, cada uno de los cuales es verdaderamente pseudoaleatorio, ^[28] y puede implementarse con esencialmente la misma cantidad de memoria que un generador lineal congruente, aunque con un poco más de cálculo .

El registro de desplazamiento de retroalimentación lineal tiene una fuerte relación con los generadores lineales congruentes. ^[29] Dados unos pocos valores en la secuencia, algunas técnicas pueden predecir los siguientes valores en la secuencia no solo para los generadores lineales congruentes, sino también para cualquier otro generador polinómico congruente.