En ciencias de la computación , multiplicar con acarreo (MWC) es un método inventado por George Marsaglia [1] para generar secuencias de números enteros aleatorios basados en un conjunto inicial de dos a muchos miles de valores semilla elegidos al azar. Las principales ventajas del método MWC son que invoca aritmética simple de números enteros por computadora y conduce a una generación muy rápida de secuencias de números aleatorios con inmensos períodos, que van desde alrededor de a .
Como ocurre con todos los generadores de números pseudoaleatorios , las secuencias resultantes son funciones de los valores semilla proporcionados.
Teoría general
Un generador de MWC es una forma especial de generador de números aleatorios de Lehmer que permite la implementación eficiente de un módulo primo mucho más grande que el tamaño de la palabra de máquina.
Las implementaciones normales del generador de Lehmer eligen un módulo cercano al tamaño de la palabra de máquina. En cambio, un generador MWC mantiene su estado en la base, entonces multiplicando por se hace implícitamente cambiando una palabra. La base se elige típicamente para igualar el tamaño de la palabra de la computadora, ya que esto hace que el módulo aritmético trivial. Esto puede variar depara un microcontrolador a. (Este artículo usa por ejemplo.)
Los valores del estado inicial ("semilla") son arbitrarios, excepto que no deben ser todos cero, ni todos en los valores máximos permitidos ( y ). (Esto se hace comúnmente eligiendo entre 1 y .). La secuencia de MWC es entonces una secuencia de pares determinado por
Esto se llama secuencia de MWC de retraso-1. A veces se prefiere una base extraña, en cuyo casose puede utilizar, que es casi tan simple de implementar. Un retrasoLa secuencia es una generalización de la secuencia lag-1 que permite períodos más largos [2] . El retraso- La secuencia de MWC es entonces una secuencia de pares (por ) determinado por
y la salida del generador MWC es la secuencia de 's,
En este caso, los valores del estado inicial ("semilla") no deben ser todos cero ni y .
El multiplicador del MWC y lag determinar el módulo . En la práctica,se elige de modo que el módulo sea primo y la secuencia tenga un período largo. Si el módulo es primo, el período de un rezago El generador de MWC es del orden de en el grupo multiplicativo de números módulo . Si bien teóricamente es posible elegir un módulo no principal, un módulo principal elimina la posibilidad de que la semilla inicial comparta un divisor común con el módulo, lo que reduciría el período del generador.
Debido a que 2 es un residuo cuadrático de números de la forma, no puede ser una raíz primitiva de . Por tanto, los generadores MWC con basetienen sus parámetros elegidos para que su período sea ( ab r −1) / 2. Ésta es una de las dificultades que supera el uso de b = 2 k - 1.
La forma básica de un generador de MWC tiene parámetros un , b y r , y r +1 palabras de estado. El estado consta de r residuos módulo b
- 0 ≤ x 0 , x 1 , x 2 , ..., x r −1 ,>
y un acarreo c r −1 < a .
Aunque la teoría de los generadores de MWC permite a > b , a casi siempre se elige más pequeño por conveniencia de implementación.
La función de transformación de estado de un generador de MWC es un paso del módulo p de reducción de Montgomery . El estado es un entero grande con la palabra más significativa c n −1 y la palabra menos significativa x n - r . Cada paso, x n - r · ( ab r −1) se suma a este número entero. Esto se hace en dos partes: −1 · x n - r se suma ax n - r , lo que da como resultado una palabra menos significativa de cero. Y en segundo lugar, una · x n - r se añade a la de transporte. Esto hace que el número entero sea una palabra más largo, produciendo dos nuevas palabras más significativas x n y c n .
Hasta ahora, esto simplemente ha agregado un múltiplo de p al estado, dando como resultado un representante diferente de la misma clase de residuo módulo p . Pero finalmente, el estado se desplaza hacia abajo una palabra, dividiendo por b . Esto descarta la palabra menos significativa de cero (que, en la práctica, nunca se calcula en absoluto) y efectivamente multiplica el estado por b −1 (mod p ).
Por lo tanto, un generador de multiplicar con acarreo es un generador de Lehmer con módulo py multiplicador b −1 (mod p ). Es lo mismo que un generador con multiplicador b , pero produce resultados en orden inverso, lo que no afecta la calidad de los números pseudoaleatorios resultantes.
Couture y L'Ecuyer [3] han demostrado el sorprendente resultado de que la celosía asociada con un generador de multiplicar con acarreo está muy cerca de la celosía asociada con el generador de Lehmer que simula. Por lo tanto, las técnicas matemáticas desarrolladas para los generadores Lehmer (como la prueba espectral ) se pueden aplicar a los generadores de multiplicación con acarreo.
Eficiencia
Un generador congruencial lineal con base b = 2 32 se implementa como
donde c es una constante. Si a ≡ 1 (mod 4) yc son impares, la secuencia congruencia de base 2 32 resultante tendrá un período 2 32 . [4]
Esto puede ser calculado utilizando sólo los bajos 32 bits del producto de una y la corriente x . Sin embargo, muchos microprocesadores pueden calcular un producto completo de 64 bits casi al mismo tiempo que el bajo de 32 bits. De hecho, muchos calculan el producto de 64 bits y luego ignoran la mitad alta.
Un generador de retardo-1 multiplicar con acarreo nos permite hacer que el período sea cercano a 263 usando casi las mismas operaciones de computadora, excepto que la mitad superior del producto de 64 bits no se ignora después de que se calcula el producto. En su lugar, se calcula una suma de 64 bits y la mitad superior se usa como un nuevo valor de acarreo c en lugar de la constante aditiva fija de la secuencia congruente estándar: Calcule ax + c en 64 bits, luego use la mitad superior como la nueva c , y la mitad inferior como la nueva x .
Elección de multiplicador
Con el multiplicador a especificado, cada par de valores de entrada x , c se convierte en un nuevo par,
Si x y c no son ambos cero, entonces el período de la secuencia resultante de multiplicar con acarreo será del orden de b = 2 32 en el grupo multiplicativo de residuos módulo ab r - 1 , es decir, el n más pequeño tal que b n ≡ 1 (mod ab r - 1).
Si p = ab r - 1 es primo, entonces el pequeño teorema de Fermat garantiza que el orden de cualquier elemento debe dividir p - 1 = ab r - 2, por lo que una forma de garantizar un orden grande es elegir a tal que p sea a " prima segura ", es decir, tanto p como ( p - 1) / 2 = ab r / 2 - 1 son primos. En tal caso, para b = 2 32 y r = 1, el período será ab r / 2 - 1, acercándose a 2 63 , que en la práctica puede ser un subconjunto aceptablemente grande del número de posibles pares de 32 bits ( x , c ).
Más específicamente, en tal caso, el orden de cualquier elemento divide p - 1, y solo hay cuatro divisores posibles: 1, 2, ab r / 2 - 1 o ab r - 2. Los dos primeros se aplican solo a la los elementos 1 y -1, y los argumentos de reciprocidad cuadrática muestran que la cuarta opción no se puede aplicar a b , por lo que solo queda la tercera opción.
A continuación se muestran algunos valores máximos de a para aplicaciones informáticas que satisfacen la condición de cebado de seguridad anterior, para generadores lag-1:
Bits en un | B | Máximo a tal que ab −1 es un primo seguro | Período |
---|---|---|---|
15 | 2 16 | 2 15 −50 = 32,718 | 1.072.103.423 |
dieciséis | 2 16 | 2 16 −352 = 65,184 | 2,135,949,311 |
31 | 2 32 | 2 31 −563 = 2,147,483,085 | 4.611.684.809.394.094.079 |
32 | 2 32 | 2 32 −178 = 4,294,967,118 | 9.223.371.654.602.686.463 |
64 | 2 64 | 2 64 −742 = 18,446,744,073,709,550,874 | 2 63 (2 64 −742) −1 ≈ 1,701 × 10 38 |
128 | 2 128 | 2 128 −10 408 | 2 127 (2 128 -10408) -1 ≈ 5,790 × 10 76 |
256 | 2 256 | 2 256 -9,166 mil | 2 255 (2 256 -9,166 mil) -1 ≈ 6,704 × 10 153 |
512 | 2 512 | 2 512 -150736 | 2 511 (2 512 -150736) -1 ≈ 8,988 × 10 307 |
Mientras que un cebado seguro asegura que casi cualquier elemento del grupo tenga un orden grande, el período del generador es específicamente del orden de b . Para módulos pequeños, se pueden usar métodos computacionalmente más costosos para encontrar multiplicadores a donde el período es ab / 2 - 1. Los siguientes son nuevamente valores máximos de a de varios tamaños.
Bits en un | b r | Máximo a tal que b tiene orden ab r / 2−1 | Período |
---|---|---|---|
8 | 2 8 | 2 8 −7 = 249 | 31,871 |
8 | (2 8 ) 2 = 2 16 | 2 8 −32 = 224 | 7.340.031 |
15 | 2 16 | 2 15 −29 = 32,739 | 1.072.791.551 |
dieciséis | 2 16 | 2 16 −22 = 65,514 | 2,146,762,751 |
8 | (2 8 ) 4 = 2 32 | 2 8 −64 = 192 | 412,316,860,415 |
15 | (2 16 ) 2 = 2 32 | 2 15 −26 = 32,742 | 70,312,909,602,815 |
dieciséis | (2 16 ) 2 = 2 32 | 2 16 −2 = 65,534 | 140,733,193,388,031 |
31 | 2 32 | 2 31 −68 = 2,147,483,580 | 4.611.685.872.398.499.839 |
32 | 2 32 | 2 32 −76 = 4.294.967.220 | 9.223.371.873.646.018.559 |
8 | (2 8 ) 8 = 2 64 | 2 8 −41 = 215 | 2 63 (2 8 −41) −1 ≈ 1.983 × 10 21 |
15 | (2 16 ) 4 = 2 64 | 2 15 −50 = 32,718 | 2 63 (2 15 −50) −1 ≈ 3,018 × 10 23 |
dieciséis | (2 16 ) 4 = 2 64 | 2 16 −56 = 65,480 | 2 63 (2 16 −56) −1 ≈ 6.039 × 10 23 |
31 | (2 32 ) 2 = 2 64 | 2 31 −38 = 2,147,483,610 | 2 63 (2 31 −38) −1 ≈ 1,981 × 10 28 |
32 | (2 32 ) 2 = 2 64 | 2 32 −43 = 4,294,967,253 | 2 63 (2 32 −43) −1 ≈ 3.961 × 10 28 |
63 | 2 64 | 2 63 −140 = 9,223,372,036,854,775,668 | 2 63 (2 63 −140) −1 ≈ 8,507 × 10 37 |
64 | 2 64 | 2 64 −116 = 18,446,744,073,709,551,500 | 2 63 (2 64 −116) −1 ≈ 1,701 × 10 38 |
Generadores de MWC como decimales periódicos
La salida de un generador de multiplicar con acarreo es equivalente a la expansión de la base - b de una fracción con denominador p = ab r - 1. Aquí hay un ejemplo para el caso simple de b = 10 y r = 1, entonces el resultado es un decimal periódico .
Empezando con , la secuencia del MWC
produce esta secuencia de estados:
- 10,01,07,49,67,55,40,04,28,58,61,13,22,16,43,25,37,52,19,64,34,31, 10,01,07, ...
con el período 22. Considere solo la secuencia de x i :
- 0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4,1, 0,1,7, 9,7,5,0, ...
Observe que si esos segmentos repetidos de valores x se colocan en orden inverso :
obtenemos la expansión j / ( ab −1) con a = 7, b = 10, j = 10 :
Esto es cierto en general: La secuencia de x s producida por un lag- r generador MWC:
cuando se pone en orden inverso, será la expansión de la raíz- b de una fracción j / ( ab r - 1) para algún 0 < j < ab r .
Equivalencia a generador congruencial lineal
Continuando con el ejemplo anterior, si comenzamos con y generar la secuencia congruencial ordinaria
- ,
obtenemos la secuencia del período 22
- 31,10,1,7,49,67,55,40,4,28,58,61,13,22,16,43,25,37,52,19,64,34, 31,10,1, 7, ...
y esa secuencia, mod reducida 10, es
- 1,0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4, 1,0,1, 7,9,7,5,0, ...
la misma secuencia de x resultante de la secuencia de MWC.
Esto es cierto en general, (pero aparentemente solo para las secuencias de MWC de lag-1 [ cita requerida ] ):
Dados los valores iniciales , la secuencia resultante de la secuencia de MWC de lag-1
es exactamente la secuencia de salida del generador de números aleatorios de Lehmer y n = ay n - 1 mod ( ab - 1), módulo reducido b .
La elección de un valor inicial diferente y 0 simplemente rota el ciclo de x .
Generadores complementarios de multiplicación con acarreo
Establecer el período de un lag- r generador de CMM por lo general implica eligiendo multiplicador de un modo que p = ab r - 1 es primo. Entonces p - 1 tendrá que factorizarse para encontrar el orden de b mod p . Si p es un primo seguro , entonces esto es simple y el orden de b será p - 1 o ( p - 1) / 2. En otros casos, p - 1 puede ser difícil de factorizar.
Sin embargo, el algoritmo también permite un multiplicador negativo . Esto conduce a una ligera modificación del procedimiento MWC y produce un módulo p = | - ab r - 1 | = ab r + 1. Esto hace que p - 1 = ab r sea fácil de factorizar, lo que hace que sea práctico establecer el período de generadores muy grandes.
El procedimiento modificado se llama complementario-multiplicar-con-acarreo (CMWC), y la configuración es la misma que para lag- r MWC: multiplicador a , base b y r + 1 semillas,
- x 0 , x 1 , x 2 , ..., x r −1 y c r −1 .
La modificación es para la generación de un nuevo par ( x , c ). Reordenando el cálculo para evitar números negativos, el nuevo valor de x se complementa restando de b - 1:
La secuencia resultante de x ' s producida por el cmwc RNG tendrá período del orden de b en el grupo multiplicativo de residuos modulo ab r 1, y la salida x ' s, en orden inverso, se formará la base b expansión de j / ( ab r +1) para algunos 0 < j < ab r .
El uso de lag- r cmwc hace que sea mucho más fácil encontrar los períodos de r ' es tan grande como 512, 1024, 2048, etc. (Haciendo r una potencia de 2 hace que sea un poco más sencillo a los elementos de acceso en la matriz que contiene la r más reciente x ' s.)
Otra ventaja de este procedimiento modificado es que el período es un múltiplo de b , por lo que la salida es exactamente equidistribuida mod b . [3] (El MWC ordinario, durante su período completo, produce cada salida posible un número igual de veces, excepto que cero se produce una vez menos, un sesgo que es insignificante si el período es lo suficientemente largo).
Una desventaja de la construcción de CMWC es que, con una base de potencia de dos, el período máximo alcanzable es menor que para un generador de MWC de tamaño similar; pierde varios bits. Por lo tanto, un generador de MWC suele ser preferible para pequeños retrasos. Esto se puede remediar usando b = 2 k −1, o eligiendo un retraso de una palabra más para compensar.
Algunos ejemplos: con b = 2 32 y a = 109111 o 108798 o 108517, el período de lag-1024 CMWC
será una · 2 32762 = ab 1 024 /64, sobre 10 9867 .
Con b = 2 32 y a = 3636507990, p = ab 1359 - 1 es un primo seguro, por lo que la secuencia MWC basada en que a tiene un período 3636507990 · 2 43487 ≈ 10 13101 .
Con b = 2 32 , un CMWC RNG con un período de registro cercano puede basarse en el primo p = 15455296 b 42658 + 1. El orden de b para ese primo es 241489 · 2 1365056 ≈ 10 410928 .
Módulos más generales
El módulo de MWC de ab r −1 se elige para hacer el cálculo particularmente simple, pero trae consigo algunas desventajas, en particular que el período es como máximo la mitad del módulo. Hay varias formas de generalizar esto, a costa de más multiplicaciones por iteración.
Primero, es posible agregar términos adicionales al producto, produciendo un módulo de la forma a r b r + a s b s −1. Esto requiere calcular c n b + x n = a r x n - r + a s x n - s . (El acarreo está limitado a una palabra si a r + a s ≤ b .)
Sin embargo, esto no soluciona el problema del período, que depende de los bits bajos del módulo. Afortunadamente, el algoritmo de reducción de Montgomery permite otros módulos, siempre que sean relativamente primos con respecto a la base b , y esto se puede aplicar para permitir un módulo de la forma a r b r - a 0 , para un amplio rango de valores a 0 . Goresky y Klapper [5] desarrollaron la teoría de estos generadores generalizados de multiplicar con acarreo, demostrando, en particular, que eligiendo un negativo a 0 y a r - a 0 < b el valor de acarreo es siempre menor que b , lo que hace que la implementación eficiente. La forma más general del módulo mejora también la calidad del generador, aunque no siempre se puede obtener un período completo.
Para implementar un generador Goresky-Klapper uno precalcula un−1
0 (mod b ), y cambia la iteración de la siguiente manera: [6]
En el caso común de que b = 2 k , un 0 debe ser impar para que exista la inversa.
Implementación
La siguiente es una implementación del algoritmo cmwc en el lenguaje de programación C . Además, en el programa se incluye una función de inicialización de muestra. En esta implementación, la base es 2 32 −1 y el rezago r = 4096. El período del generador resultante es de aproximadamente.
// C99 Generador de multiplicación complementaria con transporte #include #include #include #include // ¿Cuántos bits hay en rand ()? // https://stackoverflow.com/a/27593398 #define LOG_1 (n) (((n)> = 2)? 1: 0) #define LOG_2 (n) (((n)> = 1 << 2 )? (2 + LOG_1 ((n) >> 2)): LOG_1 (n)) #define LOG_4 (n) (((n)> = 1 << 4)? (4 + LOG_2 ((n) >> 4)): LOG_2 (n)) #define LOG_8 (n) (((n)> = 1 << 8)? (8 + LOG_4 ((n) >> 8)): LOG_4 (n)) #define LOG (n) (((n)> = 1 << 16)? (16 + LOG_8 ((n) >> 16)): LOG_8 (n)) #define BITS_TO_REPRESENT (n) (LOG (n) + !! ( (n) & ((n) - 1))) #if ((RAND_MAX | (RAND_MAX >> 1))! = RAND_MAX) #error "se esperaba un RAND_MAX que es 2 ^ n - 1!" #endif #define RAND_BITS BITS_TO_REPRESENT (RAND_MAX)// Partes de trabajo de CMWC #define CMWC_CYCLE 4096 // como Marsaglia recomienda #define CMWC_C_MAX 809430660 // como Marsaglia recomienda struct cmwc_state { uint32_t Q [ CMWC_CYCLE ]; uint32_t c ; // debe estar limitado con CMWC_C_MAX unsigned i ; };// Recoge 32 bits de rand (). Se le anima a utilizar una mejor fuente en su lugar. uint32_t rand32 ( vacío ) { uint32_t resultado = rand (); para ( int bits = RAND_BITS ; bits < 32 ; bits + = RAND_BITS ) resultado = resultado << RAND_BITS | rand (); devolver resultado ; }// Inicia el estado con semilla void initCMWC ( struct cmwc_state * state , unsigned int seed ) { srand ( semilla ); para ( int i = 0 ; i < CMWC_CYCLE ; i ++ ) estado -> Q [ i ] = rand32 (); hacer estado -> c = rand32 (); while ( estado -> c > = CMWC_C_MAX ); estado -> i = CMWC_CYCLE - 1 ; }// Motor CMWC uint32_t randCMWC ( struct cmwc_state * state ) // Parámetro EDITADO * faltaba el estado { uint64_t const a = 18782 ; // como recomienda Marsaglia uint32_t const m = 0xfffffffe ; // como recomienda Marsaglia uint64_t t ; uint32_t x ;estado -> i = ( estado -> i + 1 ) & ( CMWC_CYCLE - 1 ); t = a * estado -> Q [ estado -> i ] + estado -> c ; / * Sea c = t / 0xffffffff, x = t mod 0xffffffff * / estado -> c = t >> 32 ; x = t + estado -> c ; si ( x < estado -> c ) { x ++ ; estado -> c ++ ; } devolver estado -> Q [ estado -> i ] = m - x ; }int main () { struct cmwc_state cmwc ; semilla int sin firmar = tiempo ( NULO ); initCMWC ( & cmwc , semilla ); printf ( "CMWC aleatorio:% u \ n " , randCMWC ( & cmwc )); }
Las siguientes son implementaciones de generadores MWC de estado pequeño con salida de 64 bits utilizando multiplicaciones de 128 bits.
// C99 + __uint128_t MWC, 128 bits de estado, período aprox. 2 ^ 127/ * El estado no debe ser ni todo cero, ni x = 2 ^ 64 - 1, c = MWC_A1 - 1. La condición 0 * / uint64_t x , c = 1 ;#define MWC_A1 0xff3a275c007b8ee6uint64_t en línea next () { const __uint128_t t = MWC_A1 * ( __uint128_t ) x + c ; c = t >> 64 ; return x = t ; }
// C99 + __uint128_t MWC, 256 bits de estado, período aprox. 2 ^ 255/ * El estado no debe ser ni todo cero, ni x = y = z = 2 ^ 64 - 1, c = MWC_A3 - 1. Por tanto, la condición 0 * / uint64_t x , y , z , c = 1 ;#define MWC_A3 0xff377e26f82da74auint64_t en línea next () { const __uint128_t t = MWC_A3 * ( __uint128_t ) x + c ; x = y ; y = z ; c = t >> 64 ; return z = t ; }
Las siguientes son implementaciones de los generadores MWC generalizados de Goresky-Klapper de estado pequeño con salida de 64 bits usando multiplicaciones de 128 bits.
// C99 + __uint128_t Goresky-Klapper GMWC, 128 bits de estado, período aprox. 2 ^ 127/ * El estado no debe ser ni todo cero, ni x = 2 ^ 64 - 1, c = GMWC_A1 + GMWC_MINUS_A0. Por tanto, la condición 0 suficiente. * /uint64_t x = 0 , c = 1 ;#define GMWC_MINUSA0 0x7d084a4d80885f #define GMWC_A0INV 0x9b1eea3792a42c61 #define GMWC_A1 0xff002aae7d81a646uint64_t en línea next () { const __uint128_t t = GMWC_A1 * ( __uint128_t ) x + c ; x = GMWC_A0INV * ( uint64_t ) t ; c = ( t + GMWC_MINUSA0 * ( __uint128_t ) x ) >> 64 ; return x ; }
// C99 + __uint128_t Goresky-Klapper GMWC, 256 bits de estado, período aprox. 2 ^ 255/ * El estado no debe ser ni todo cero, ni x = y = z = 2 ^ 64 - 1, c = GMWC_A3 + GMWC_MINUS_A0. Por tanto, la condición 0 es suficiente. * /uint64_t x , y , z , c = 1 ; / * El estado se puede sembrar con cualquier conjunto de valores, no todos los ceros. * /#define GMWC_MINUSA0 0x54c3da46afb70f #define GMWC_A0INV 0xbbf397e9a69da811 #define GMWC_A3 0xff963a86efd088a2uint64_t en línea next () { const __uint128_t t = GMWC_A3 * ( __uint128_t ) x + c ; x = y ; y = z ; z = GMWC_A0INV * ( uint64_t ) t ; c = ( t + GMWC_MINUSA0 * ( __uint128_t ) z ) >> 64 ; return z ; }
Uso
Debido a la simplicidad, la velocidad, la calidad (pasa muy bien las pruebas estadísticas) y el período asombroso, se sabe que CMWC se usa en el desarrollo de juegos, particularmente en los juegos roguelike modernos . Se la conoce informalmente como la Madre de todos los PRNG, un nombre acuñado originalmente por el propio Marsaglia. [7] En libtcod, CMWC4096 reemplazó MT19937 como el PRNG predeterminado. [8]
Ver también
Referencias
- ^ Marsaglia, George ; Zaman, Arif (agosto de 1995). "El CDROM de números aleatorios de Marsaglia, incluida la batería de pruebas de aleatoriedad" . Cite journal requiere
|journal=
( ayuda ) - ^ Marsaglia, George¨ (mayo de 2003). "Generadores de números aleatorios" . Revista de métodos estadísticos aplicados modernos . 2 (1): 2-13. doi : 10.22237 / jmasm / 1051747320 .
- ^ a b Couture, Raymond; L'Ecuyer, Pierre (abril de 1997). "Propiedades de distribución de los generadores de números aleatorios Multiply-with-carry" (PDF) . Matemáticas de la Computación . 66 (218): 591–607. Código Bibliográfico : 1997MaCom..66..591C . CiteSeerX 10.1.1.154.331 . doi : 10.1090 / S0025-5718-97-00827-2 .
Veremos que, para el MWC complementario, cada bit del valor de salida es justo, es decir, los dos dígitos binarios aparecerán con la misma frecuencia en un período completo, una propiedad que no comparten los generadores de MWC.
- ^ Hull, 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 .
- ^ a b Goresky, Mark ; Klapper, Andrew (octubre de 2003). "Generadores de números aleatorios de multiplicación con acarreo eficientes con período máximo" (PDF) . Transacciones ACM sobre modelado y simulación por computadora . 13 (4): 310–321. CiteSeerX 10.1.1.4.9190 . doi : 10.1145 / 945511.945514 .
- ^ Nótese que el artículo de Goresky y Klapper [5] contiene un error en la ecuación (4): la última igualdad no es verdadera; no se puede eliminar el segundo sumando del cálculo del acarreo.
- ^ "Madre de todos los generadores de números aleatorios de Marsaglia" . home.sandiego.edu .
- ^ "Generador de números aleatorios - RogueBasin" . www.roguebasin.com . Consultado el 30 de noviembre de 2016 .
- Marsaglia, George (4 de julio de 2003). "Xorshift RNG" . Revista de software estadístico . 8 (14): 1–6. doi : 10.18637 / jss.v008.i14 .
- Marsaglia, George (octubre de 2005). "Sobre la aleatoriedad de Pi y otras expansiones decimales" . Interstat . CiteSeerX 10.1.1.694.4783 .
- Prensa, William H .; Teukolsky, Saul A .; Vetterling, William T .; Flannery, Brian P. (2007). "Sección 7.1.2.B Multiplicar con acarreo (MWC)" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.