Generador de números pseudoaleatorios con multiplicación y acarreo

En informática , la multiplicación con acarreo (MWC) es un método inventado por George Marsaglia ^{[ 1 ]} para generar secuencias de enteros aleatorios a partir de un conjunto inicial de entre dos y miles de valores semilla elegidos aleatoriamente. Implica aritmética de enteros computacional simple y conduce a la generación de alta velocidad de secuencias de números aleatorios con períodos inmensos (que van desde aproximadamente${\displaystyle 2^{60}}$a${\displaystyle 2^{2,000,000}}$); esas son sus principales ventajas.

Al igual que ocurre con todos los generadores de números pseudoaleatorios , las secuencias resultantes son funciones de los valores semilla proporcionados.

Un generador MWC es una forma especial de generador de números aleatorios de Lehmer.${\displaystyle x_{n}=bx_{n-1}{\bmod {p}}}$lo que permite una implementación eficiente de un módulo primo${\displaystyle p}$mucho mayor que el tamaño de palabra de la máquina.

Las implementaciones normales del generador Lehmer eligen un módulo cercano al tamaño de palabra de la máquina. Un generador MWC, en cambio, mantiene su estado en base.${\displaystyle b}$, por lo tanto, multiplicando por${\displaystyle b}$se hace implícitamente desplazando una palabra. La base${\displaystyle b}$Por lo general, se elige para que sea igual al tamaño de palabra de la computadora, ya que esto hace que la aritmética módulo${\displaystyle b}$trivial. Esto puede variar de${\displaystyle b=2^{8}}$para un microcontrolador a${\displaystyle b=2^{64}}$. (Este artículo utiliza${\displaystyle b=2^{32}}$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 (${\displaystyle x_{0}=b-1}$y${\displaystyle c_{0}=a-1}$). (Esto se suele hacer eligiendo ${\displaystyle c_{0}}$entre 1 y${\displaystyle a-2}$.). La secuencia MWC es entonces una secuencia de pares${\displaystyle x_{n},c_{n}}$determinado por

${\displaystyle x_{n}=(ax_{n-1}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-1}+c_{n-1}}{b}}\right\rfloor }$

Esto se denomina secuencia MWC de retraso 1. A veces se prefiere una base impar, en cuyo caso${\displaystyle b=2^{k}-1}$se puede utilizar, lo cual es casi tan simple de implementar. Un retraso-${\displaystyle r}$La secuencia es una generalización de la secuencia de retardo 1 que permite períodos más largos ^{[ 2 ]} . El retardo-${\displaystyle r}$La secuencia MWC es entonces una secuencia de pares ${\displaystyle x_{n},c_{n}}$(para${\displaystyle n>r}$) determinado por

${\displaystyle x_{n}=(ax_{n-r}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor }$

y la salida del generador MWC es la secuencia de${\displaystyle x}$'s,

${\displaystyle x_{r},x_{r+1},x_{r+2},...}$

En este caso, los valores del estado inicial ("semilla") no deben ser todos cero ni${\displaystyle x_{0}=b-1}$y${\displaystyle c_{r-1}=a-1}$.

El multiplicador MWC${\displaystyle a}$y retraso${\displaystyle r}$determinar el módulo${\displaystyle p=ab^{r}-1}$En la práctica,${\displaystyle a}$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 retardo-${\displaystyle r}$El generador MWC es del orden de${\displaystyle b}$en el grupo multiplicativo de números módulo${\displaystyle p}$Aunque teóricamente es posible elegir un módulo no primo, un módulo primo 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.

Porque 2 es un residuo cuadrático de números de la forma${\displaystyle 8k\pm 1}$,${\displaystyle b=2^{k}}$no puede ser una raíz primitiva de${\displaystyle p=ab^{r}-1}$Por lo tanto, los generadores MWC con base${\displaystyle 2^{k}}$tienen sus parámetros elegidos de modo que su período sea ( ab ^r −1)/2. Esta es una de las dificultades que supera el uso de b = 2 ^k  − 1. 

La forma básica de un generador MWC tiene parámetros a , b y r , y r + 1 palabras de estado. El estado consta de r residuos módulo b.

0 ≤ x ₀ , x ₁ , x ₂ ,..., x _{r −1} < b,

y un acarreo c _{r −1} < a .  

Aunque la teoría de los generadores MWC permite a > b , casi siempre se elige a menor por conveniencia de implementación .  

La función de transformación de estado de un generador MWC es un paso de reducción de Montgomery módulo p . El estado es un entero grande con la palabra más significativa c _{n −1} y la palabra menos significativa x _{n − r} . En cada paso, x _{n − r} ·( ab ^r −1) se suma a este entero. Esto se hace en dos partes: −1· x _{n − r} se suma a x _{n − r} , lo que resulta en una palabra menos significativa de cero. Y segundo, a · x _{n − r} se suma al acarreo. Esto hace que el entero sea una palabra más largo, produciendo dos nuevas palabras más significativas x _n y c _n .

Hasta ahora, esto simplemente ha añadido un múltiplo de p al estado, lo que da como resultado un representante diferente de la misma clase de residuo módulo p . Pero finalmente, el estado se desplaza una palabra hacia abajo, dividiéndolo por b . Esto descarta la palabra menos significativa de cero (que, en la práctica, nunca se calcula) y efectivamente multiplica el estado por b ⁻¹ (mod p ).

Así, un generador de multiplicación con acarreo es un generador de Lehmer con módulo p y multiplicador b ⁻¹ (mod p ). Esto es lo mismo que un generador con multiplicador b , pero produce la salida en orden inverso, lo que no afecta la calidad de los números pseudoaleatorios resultantes.

Couture y L'Ecuyer ^{[ 3 ]} demostraron el sorprendente resultado de que la red asociada a un generador de multiplicación con acarreo es muy similar a la red asociada al generador de Lehmer que simula. Por lo tanto, las técnicas matemáticas desarrolladas para los generadores de Lehmer (como la prueba espectral ) pueden aplicarse a los generadores de multiplicación con acarreo.

Se implementa un generador congruencial lineal con base b = 2 ^{32 como}

${\displaystyle x_{n+1}=(ax_{n}+c)\ {\bmod {\,}}2^{32},}$

donde c es una constante. Si a ≡ 1 (mod 4) y c es impar, la secuencia congruencial resultante en base 2 ³² tendrá un período de 2 ³² . ^{[ 4 ]}

Esto se puede calcular utilizando solo los 32 bits menos significativos del producto de a y el valor actual de x . Sin embargo, muchos microprocesadores pueden calcular un producto completo de 64 bits en casi el mismo tiempo que los 32 bits menos significativos. De hecho, muchos calculan el producto de 64 bits y luego ignoran la mitad superior.

Un generador de multiplicación con acarreo de retardo 1 nos permite hacer que el período sea casi 2 ⁶³ 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 cambio, 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 congruencial estándar: Calcular ax + c en 64 bits, luego usar la mitad superior como el nuevo c , y la mitad inferior como el nuevo x .

Con el multiplicador a especificado, cada par de valores de entrada x , c se convierte en un nuevo par,

${\displaystyle x\leftarrow (ax+c)\,{\bmod {\,}}2^{32},\ \ c\leftarrow \left\lfloor {\frac {ax+c}{2^{32}}}\right\rfloor .}$

Si x y c no son ambos cero, entonces el período de la secuencia de multiplicación con acarreo resultante será del orden de b = 2 ³² en el grupo multiplicativo de residuos módulo ab ^r  −  1 , es decir, el n más pequeño tal que b ⁿ ≡ 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 asegurar un orden grande es elegir a tal que p sea un " primo seguro ", es decir, tanto p como ( p  −  1)/2 = ab ^r /2  −  1 son primos. En tal caso, para b = 2 ³² y r = 1, el período será ab ^r /2  −  1, aproximándose a 2 ⁶³ , que en la práctica puede ser un subconjunto aceptablemente grande del número de pares posibles de 32 bits ( x , c ).

Más específicamente, en tal caso, el orden de cualquier elemento divide a 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 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 primo seguro anterior, para generadores de retardo 1:

Si bien un número primo seguro garantiza 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. A continuación se muestran nuevamente los valores máximos de a de varios tamaños.

La salida de un generador de multiplicación con acarreo es equivalente a la expansión en 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, por lo que el resultado es un decimal periódico .

Comenzando con${\textstyle c_{0}=1,x_{0}=0}$, la secuencia MWC

${\displaystyle x_{n}=(7x_{n-1}+c_{n-1})\,{\bmod {\,}}10,\ c_{n}=\left\lfloor {\frac {7x_{n-1}+c_{n-1}}{10}}\right\rfloor ,}$

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 periodo 22. Consideremos 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 :

${\displaystyle 1449275\cdots 9710\,1449275\cdots 9710\,144\cdots }$

obtenemos la expansión j /( ab −1) con a =7, b =10, j=10 :

${\displaystyle {\frac {10}{69}}=0.1449275362318840579710\,14492753623\ldots }$

Esto es cierto en general: La secuencia de x producida por un generador MWC con retardo r :

${\displaystyle x_{n}=(ax_{n-r}+c_{n-1}){\bmod {\,}}b\,,\ \ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor ,}$

cuando se coloca en orden inverso, será la expansión en base b de una fracción j /( ab ^r − 1) para algún 0 < j < ab ^r .  

Continuando con el ejemplo anterior, si comenzamos con${\textstyle x_{0}=34}$y generar la secuencia congruencial ordinaria

${\displaystyle x_{n}=7x_{n-1}\,{\bmod {\,}}69}$,

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, reducida módulo 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 MWC.

Esto es cierto en general (pero aparentemente solo para secuencias MWC de retraso 1 ):

Dados los valores iniciales${\displaystyle x_{0},c_{0}}$, la secuencia${\displaystyle x_{1},x_{2},\ldots }$como resultado de la secuencia MWC de retraso 1

${\displaystyle x_{n}=(ax_{n-1}+c_{n-1})\,{\bmod {b}}\,,\ \ c_{n}=\left\lfloor {\frac {ax_{n-1}+c_{n-1}}{b}}\right\rfloor }$

es exactamente la secuencia de salida del generador de números aleatorios de Lehmer y _n = ay _{n − 1}   mod ( ab − 1), reducida módulo b .  

Elegir un valor inicial diferente y ₀ simplemente rota el ciclo de x' .

Para determinar el período de un generador MWC con retardo r , generalmente se elige un multiplicador a tal que p = ab ^r  −  1 sea primo. Luego, p  −  1 deberá factorizarse para hallar el orden de b mod p . Si p es un primo seguro , esto es sencillo, 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 conlleva 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 permite determinar el período de generadores muy grandes.

El procedimiento modificado se llama multiplicación complementaria con acarreo (CMWC), y la configuración es la misma que para MWC con retardo r : multiplicador a , base b y semillas r  + 1, 

x ₀ , x ₁ , x ₂ , ..., x _{r −1} , y c _{r −1} .

La modificación consiste en la generación de un nuevo par ( x , c ). Reorganizando el cálculo para evitar números negativos, el nuevo valor de x se complementa restándolo de b  −  1:

${\displaystyle x_{n}=(b-1)-(ax_{n-r}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor .}$

La secuencia resultante de x 's producida por el generador de números aleatorios CMWC tendrá un período del orden de b en el grupo multiplicativo de residuos módulo ab ^r +1, y la salida x 's , en orden inverso, formará la expansión en base b de j /( ab ^r +1) para algún 0  < j < ab ^r .   

El uso de lag -r CMWC facilita mucho la búsqueda de periodos para valores de r tan grandes como 512, 1024, 2048, etc. (Hacer que r sea una potencia de 2 simplifica ligeramente el acceso a los elementos del array que contienen los r valores de x más recientes ).

Otra ventaja de este procedimiento modificado es que el período es un múltiplo de b , por lo que la salida está exactamente equidistribuida módulo b . ^{[ 3 ]} (El MWC ordinario, durante todo su período, produce cada salida posible un número igual de veces, excepto que el cero se produce una vez menos, un sesgo que es despreciable si el período es lo suficientemente largo).

Una desventaja de la construcción CMWC es que, con una base que es potencia de dos, el período máximo alcanzable es menor que el de un generador MWC de tamaño similar; se pierden varios bits. Por lo tanto, un generador MWC suele ser preferible para pequeños retardos. Esto se puede solucionar utilizando b = 2k ⁻ 1, o eligiendo un retardo una palabra mayor para compensar.

Algunos ejemplos: Con b = 2 ³² y a = 109111 o 108798 o 108517, el período del CMWC de retardo 1024

${\displaystyle x_{n}=(b-1)-(ax_{n-1024}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-1024}+c_{n-1}}{b}}\right\rfloor .}$

será un ·2 ³²⁷⁶² = ab ¹⁰²⁴ /64, aproximadamente 10 ⁹⁸⁶⁷ .

Con b = 2 ³² y a = 3636507990, p = ab ¹³⁵⁹  −  1 es un primo seguro, por lo que la secuencia MWC basada en que a tiene un período de 3636507990·2 ⁴³⁴⁸⁷ ≈ 10 ¹³¹⁰¹ .

Con b = 2 ³² , un CMWC RNG con un período cercano al récord puede basarse en el primo p = 15455296 b ⁴²⁶⁵⁸  +  1. El orden de b para ese primo es 241489·2 ^1365056 ≈ 10 ⁴¹⁰⁹²⁸ .

El módulo MWC de ab ^r −1 se elige para simplificar el cálculo, pero conlleva algunas desventajas, principalmente que el período es como máximo la mitad del módulo. Existen varias maneras de generalizar esto, a costa de realizar más multiplicaciones por iteración.

En primer lugar, es posible añadir términos adicionales al producto, obteniendo 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 se limita 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 la base b , y esto se puede aplicar para permitir un módulo de la forma a _r b ^r − a ₀ , para un amplio rango de valores a ₀ . Goresky y Klapper ^{[ 5 ]} desarrollaron la teoría de estos generadores generalizados de multiplicación con acarreo, demostrando, en particular, que al elegir un a ₀ negativo y a _r – a ₀ < b el valor del acarreo siempre es menor que b , lo que hace que la implementación sea eficiente. La forma más general del módulo también mejora la calidad del generador, aunque no siempre se puede obtener el período completo.

Para implementar un generador de Goresky-Klapper se precalcula a ⁻¹ ₀  (mod b ), y se cambia la iteración de la siguiente manera: ^{[ 6 ]} 

${\displaystyle t=c_{n-1}+\sum _{1}^{r}a_{i}x_{n-i},\ x_{n}=a_{0}^{-1}t{\bmod {b}},\ c_{n}=\left\lfloor {\frac {t-a_{0}x_{n}}{b}}\right\rfloor .}$

En el caso común de que _b = 2k ^, a0 debe ser impar para que exista el inverso.

A continuación se presenta una implementación del algoritmo CMWC en el lenguaje de programación C. El programa también incluye una función de inicialización de ejemplo. En esta implementación, la base es 2³² ⁻ 1 y el retardo r = 4096. El período del generador resultante es aproximadamente${\displaystyle 2^{131104}}$.

// Generador de multiplicación complementaria con acarreo C99 #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <time.h>// ¿Cuántos bits tiene 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 recomienda Marsaglia #define CMWC_C_MAX 809430660 // como recomienda Marsaglia struct cmwc_state { uint32_t Q [ CMWC_CYCLE ]; uint32_t c ; // debe limitarse con CMWC_C_MAX unsigned i ; };// Recopila 32 bits de rand(). Se recomienda usar una fuente mejor. uint32_t rand32 ( void ) { uint32_t result = rand (); for ( int bits = RAND_BITS ; bits < 32 ; bits += RAND_BITS ) result = result << RAND_BITS | rand (); return result ; }// Inicializa el estado con la semilla void initCMWC ( struct cmwc_state * state , unsigned int seed ) { srand ( seed ); for ( int i = 0 ; i < CMWC_CYCLE ; i ++ ) state -> Q [ i ] = rand32 (); do state -> c = rand32 (); while ( state -> c >= CMWC_C_MAX ); state -> i = CMWC_CYCLE - 1 ; }// Motor CMWC uint32_t randCMWC ( struct cmwc_state * state ) // El parámetro *state estaba ausente { 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 ++ ; } return estado -> Q [ estado -> i ] = m - x ; }int main () { struct cmwc_state cmwc ; unsigned int seed = time ( NULL );initCMWC ( & cmwc , seed ); printf ( "CMWC aleatorio: %u \n " , randCMWC ( & cmwc )); }

A continuación se muestran implementaciones de generadores MWC de estado pequeño con salida de 64 bits mediante multiplicaciones de 128 bits.

// C99 + __uint128_t MWC, 128 bits de estado, período aprox. 2^127/* El estado no debe ser ni completamente cero, ni x = 2^64 - 1, c = MWC_A1 -  1. Por lo tanto, la condición 0 < c < MWC_A1 - 1 es suficiente. */uint64_t x , c = 1 ;#define MWC_A1 0xff3a275c007b8ee6uint64_t inline 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 completamente cero, ni x = y = z = 2^64 - 1, c =  MWC_A3 - 1. Por lo tanto, la condición 0 < c < MWC_A3 - 1 es suficiente. */uint64_t x , y , z , c = 1 ;#definir MWC_A3 0xff377e26f82da74auint64_t inline next () { const __uint128_t t = MWC_A3 * ( __uint128_t ) x + c ; x = y ; y = z ; c = t >> 64 ; return z = t ; }

A continuación se presentan implementaciones de generadores MWC generalizados de Goresky-Klapper de estados pequeños con salida de 64 bits mediante 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 completamente cero, ni x = 2^64 - 1, c = GMWC_A1 +  GMWC_MINUS_A0. Por lo tanto, la condición 0 < c < GMWC_A1 + GMWC_MINUS_A0 es  suficiente. */uint64_t x = 0 , c = 1 ;#define GMWC_MINUSA0 0x7d084a4d80885f #define GMWC_A0INV 0x9b1eea3792a42c61 #define GMWC_A1 0xff002aae7d81a646uint64_t inline 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 completamente cero, ni x = y = z = 2^64 - 1, c =  GMWC_A3 + GMWC_MINUS_A0.  Por lo tanto, la condición 0 < c < GMWC_A3 + GMWC_MINUS_A0 es suficiente. */uint64_t x , y , z , c = 1 ; /* El estado puede inicializarse con cualquier conjunto de valores, no todos ceros. */#definir GMWC_MINUSA0 0x54c3da46afb70f #definir GMWC_A0INV 0xbbf397e9a69da811 #definir GMWC_A3 0xff963a86efd088a2uint64_t inline 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 ; }

Debido a su simplicidad y velocidad, CMWC es conocido por su uso en el desarrollo de videojuegos, particularmente en juegos roguelike modernos . Se le conoce informalmente como la Madre de todos los PRNG, un nombre acuñado originalmente por el propio Marsaglia. ^{[ 7 ]} En libtcod, CMWC4096 reemplazó a MT19937 como PRNG predeterminado. ^{[ 8 ]}

• Tornado de Mersenne
• Lista de generadores de números aleatorios

• Marsaglia, George (4 de julio de 2003). "Xorshift RNGs" . Journal of Statistical Software . 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 . 
• Press, William H.; Teukolsky , Saul A .; Vetterling, William T.; Flannery, Brian P. (2007). «Sección 7.1.2.B Multiplicación con acarreo (MWC)» . Numerical Recipes: The Art of Scientific Computing (3.ª  ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.