Multiplicación con acarreo

En ciencias de la computación, la multiplicación con acarreo (MWC de las siglas en inglés de multiply-with-carry) es un método creado por George Marsaglia para generar secuencias de números enteros aleatorios basados en un conjunto inicial de dos a miles de valores semilla seleccionados aleatoriamente. Las principales ventajas del método MWC son que usa simple aritmética computacional de enteros y produce una rápida generación de secuencias de números aleatorios con términos de gran tamaño, dentro del rango aproximado de 2⁶⁰ a 2^2000000.

Al igual que sucede con la mayoría de los generadores de números pseudoaleatorios, las secuencias resultantes están en función de los valores semilla seleccionados aleatoriamente.

Teoría general[editar]

Una secuencia MWC está basada en un módulo de aritmética en base b, usualmente b = 2³², dado que dicho módulo en base b es automático en muchas computadoras. Sin embargo, a veces es usada una base b = 2³² − 1, porque la aritmética para módulos 2³² − 1 requiere solamente un ajuste simple hacia 2³², y la teoría para las secuencia MWC basadas en módulos 2³² presenta algunas dificultades muy molestas que pueden ser evitadas usando b = 2³² − 1. En su forma más común, un generador lag-r MWC requiere una base b, un multiplicador a, y un conjunto de r+1 valores semilla aleatorios, consistente en r residuos de b,

x₀, x₁, x₂,..., x_r−1,

y un acarreo inicial cr−1 < a.

La secuencia lag-r MWC es entonces una secuencia de pares x_n, c_n determinada por

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

y la salida del generador MWC es la secuencia de x's,

x_r, x_r+1, x_r+2,...

El período de un generador lag-r MWC es el orden de b en el grupo multiplicativo de números módulo ab^r − 1. Es habitual escoger a tal que p = ab^r − 1 es un primo para el cual el orden de b puede ser determinado. Ya que 2 es un residuo cuadrático de números de la forma 8k±1, b = 2³² no puede ser una raíz primitiva de p = ab^r − 1. Por consiguiente no hay generadores MWC en base 2³² que presentan el período máximo posible, una de las dificultades que el uso de b = 2³² − 1 supera.

Un problema teórico con generadores MWC, indicado por Couture e l'Ecuyer (1997) es que los bits más significativos son levemente sesgados; los generadores de multiplicación con acarreo complementaria no comparten este problema: "Podemos ver que, para el MWC complementario, cada bit del valor de salida es justo, esto es, los dos dígitos binarios aparecerán con igual frecuencia en un período completo, una propiedad no compartida por generadores MWC." Los generadores de multiplicación con acarreo complementarios también requieren considerablemente más tiempo de cómputo por iteración, de tal manera que existe un compromiso de evaluar en dependencia de los requisitos de la implementación.

Comparación con generadores de congruencia lineales[editar]

Los generadores de congruencia lineales son implementados como

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

ya que la mayoría de los procesadores aritméticos son capaces de poner el multiplicador a y el x actual en registros de 32-bit, formando el producto en registros contiguos de 64 bits, y tomando los 32 bits inferiores como el producto, o sea, de forma

a\times x\ {\bmod {\,}}2^{32}

.

Agregando el c de 32-bit a esa mitad inferior se obtiene (ax+c) mod 2³². Si a mod 8 es 1 o 5 y c es impar, la secuencia congruente resultante base 2³² tendrá un período 2³².

Un generador lag-1 de multiplicación con acarreo nos permite hacer el período aproximadamente 2⁶³ usando esas mismas operaciones computacionales, excepto que esta vez la mitad superior del producto de 64 bits es usada en vez de ignorada, después de que los 64 bits son formados. Es usado como un nuevo valor de acarreo c en vez del valor fijo de acarreo de la secuencia de congruencial estándar: tomando ax+c en 64-bits, luego formando un nuevo c con la mitad superior de esos 64 bits, y el nuevo x con la mitad inferior.

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

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

Si x y c no son cero ambos, entonces el período de la secuencia de multiplicación con acarreo resultante será de orden b = 2³² en el grupo multiplicativo de residuales módulo ab − 1, o sea, en menor n tal que bⁿ = 1 mod (ab − 1). Si escogemos a entre 28 y 31 bits tal que ab−1 es un "primo seguro", que ambos ab − 1 y ab/2 − 1 son primos, entonces el período será ab/2 − 1, acercándose a 2⁶³, lo cual en la práctica puede ser un subconjunto aceptablemente grande de posibles pares (x, c) de números de 32.

A continuación algunos valores máximos de a para aplicaciones computacionales que satisfacen la condición de primo seguro citada anteriormente:

Bits en a	b	Máximo a tal que ab−1 es un Primo Seguro	Período
15	2¹⁶	2¹⁵−50 = 32,718	1,072,103,423
16	2¹⁶	2¹⁶−352 = 65,184	2,135,949,311
31	2³²	2³¹−563 = 2,147,483,085	4,611,684,809,394,094,079
32	2³²	2³²−178 = 4,294,967,118	9,223,371,654,602,686,463
64	2⁶⁴	2⁶⁴−742 = 18,446,744,073,709,550,874	170,141,183,460,469,224,887,945,252,369,640,456,191
128	2¹²⁸	2¹²⁸−10,408	2¹²⁷(2¹²⁸−10,408)−1
256	2²⁵⁶	2²⁵⁶−9166	2²⁵⁵(2²⁵⁶−9166)−1
512	2⁵¹²	2⁵¹²−150,736	2⁵¹¹(2⁵¹²−150,736)-1

Sin embargo, como ser un primo seguro no afecta la aleatoriedad de la secuencia, simplemente se puede escoger a tal que el orden de b sea ab/2 − 1. La siguiente tabla refleja los valores máximos de a para varios tamaños.

Bits en a	b	Máximo a tal que b tiene orden ab/2−1	Período
15	2¹⁶	2¹⁵−29 = 32,739	1,072,791,551
16	2¹⁶	2¹⁶−22 = 65,514	2,146,762,751
31	2³²	2³¹−68 = 2,147,483,580	4,611,685,872,398,499,839
32	2³²	2³²−76 = 4,294,967,220	9,223,371,873,646,018,559
63	2⁶⁴	2⁶³−140 = 9,223,372,036,854,775,668	85,070,591,730,234,614,574,571,566,698,273,439,743
64	2⁶⁴	2⁶⁴−116 = 18,446,744,073,709,551,500	170,141,183,460,469,230,661,776,147,440,730,111,999

Se muestra una comparación de secuencias de congruentes y MWC para el simple caso de la aritmética módulo 10; donde los "registros" tienen un solo dígito, y los registros contiguos dos dígitos:

Comenzando con $x_{0}=1$ , la secuencia congruencial

x_{n}=(7x_{n-1}+3)\,{\bmod {\,}}10,

tiene esta secuencia de registros contiguos:

10,03,24,31,10,03,24,31,10,\ldots ,

y la secuencia de salida de x's, (el registro más a la derecha), tiene período 4:

0,3,4,1,0,3,4,1,0,3,4,1,\ldots

Iniciando con $x_{0}=1,c_{0}=3$ , la secuencia MWC

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

tiene esta secuencia de registros contiguos:

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 secuencia de salida de x's teniendo período 22:

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,...

Note que si esos segmentos repetidos de valores de x son colocados en orden inverso a partir de un $x_{22n+20}$ ,

449275\cdots 97101\,449275\cdots 9710144\cdots

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

{\frac {31}{69}}=.4492753623188405797101\,4492753623\ldots

Esto es generalmente verdadero: La secuencia de x's producida por un generador lag-r MWC:

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 lo ponemos en orden inverso, tendremos la expansión base-b de un racional j/(ab^r − 1) para algún 0 < j < ab^r.

Note además que si, empezando con $x_{0}=34$ , generamos la secuencia congruencial ordinaria

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

,

tenemos la secuencia de 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 mod 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's resultante de la secuencia MWC.

Generalmente esto es verdad, (pero aparentemente solo para secuencias lag-1 MWC):

Dados los valores iniciales $x_{0},c_{0}$ , la secuencia $x_{1},x_{2},\ldots$ resultante de la secuencia lag-1 MWC

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 congruencial y_n = ay_n − 1 mod(ab − 1), reducida módulo b. La elección del valor inicial y₀ meramente rota el ciclo de x's.

Generadores de Multiplicación con Acarreo Complementaria[editar]

Estableciendo el período de un generador lag-r MWC usualmente implica escoger un multiplicador a tal que p=ab^r − 1 es primo. Si p es un primo seguro, entonces el orden de b será p − 1 or (p − 1)/2. De otro modo, es probable que p − 1 tendrá que ser factorizado para encontrar el orden de b mod p, and p = ab^r − 1 puede ser difícil de factorizar.

Pero un primo de la forma p = ab^r + 1 será p−1 fácil de factorizar, de esta manera una versión de multiplicación con acarreo que involucra el orden de b para un primo p = ab^r + 1 reducirá considerablemente el número de teoría computacional requerida establecer el período de una secuencia MWC.

Afortunadamente, una modificación leve del procedimiento MWC conduce a primos de la forma ab^r + 1. El nuevo procedimiento es llamado multiplicación con acarreo complementaria (CMWC de las siglas en inglés de complementary-multiply-with-carry ), y el esquema es el mismo que para el lag-r MWC: multiplicador a, base b, r + 1 semillas

x₀, x₁, x₂,..., x_r−1, y c_r − 1.

Hay un cambio leve en la generación de un nuevo par (x, c): $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 .$

Esto es, tomando el complemento, (b−1)−x, al formar el nuevo x.

La secuencia resultante de x`s producida por el CMWC RNG tendrá como período el orden de b en el grupo multiplicativo de residuales módulo ab^r+1, y la salida x`s, en orden inverso, formará la base b expansión de j/(ab^r+1) para algún 0<j<ab^r. Lo hace ligeramente más fácil (y más rápido) para ganar acceso a elementos en el array conteniendo a la r más reciente

El uso de lag-r CMWC hace mucho más fácil encontrar períodos para r`s tan largos como 512, 1024, 2048, etc. (Tomando r como una potencia de 2 hace ligeramente más fácil (y rápido) acceder a los elementos en el array conteniendo el r-ésimo más reciente x`s.)

Algunos ejemplos:

Con b=2³², el período del lag-1024 CMWC

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á a $\cdot$ 2³²⁷⁶², acerca de 10⁹⁸⁶⁷ para estos tres as: 109111 o 108798 o 108517.

Con b = 2³² y a = 3636507990, p = ab¹³⁵⁹ − 1 un primo seguro, entonces la secuencia MWC basada en esa a tiene período 3636507990 $\cdot$ 2⁴³⁴⁸⁷ $\approx$ 10¹³¹⁰¹.

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

Implementación[editar]

La implementación siguiente del algoritmo CMWC está en C (lenguaje de programación). Además, incluye en el programa una función de inicialización de muestra. En esta implementación lag r=4096 y el período del generador resultante es aproximadamente $2^{131104}$ .

#include <stdint.h>

#define PHI 0x9e3779b9

static uint32_t Q[4096], c = 362436;

void init_rand(uint32_t x)
{
	int i;

	Q[0] = x;
	Q[1] = x + PHI;
	Q[2] = x + PHI + PHI;

	for (i = 3; i < 4096; i++)
		Q[i] = Q[i - 3] ^ Q[i - 2] ^ PHI ^ i;
}

uint32_t rand_cmwc(void)
{
	static uint32_t i = 4095;
	uint64_t t;

	i = (i + 1) & 4095;
	t = (18705ULL * Q[i]) + c;
	c = t >> 32;
	Q[i] = 0xfffffffe - t;

	return Q[i];
}

Véase también[editar]

Generador de números pseudoaleatorios

Referencias[editar]

Marsaglia, G.; Zaman, A. (1991). «A new class of random number generators». Annals of Applied Probability 1 (3): 462-480. doi:10.1214/aoap/1177005878.
Marsaglia, G. (2003). «Random number generators». Journal of Modern Applied Statistical Methods 2.
Marsaglia, George (2003). «Xorshift RNGs». Journal of Statistical Software 8 (14): 1-6.
Marsaglia, G. (2005). «On the randomness of Pi and other decimal expansions». Interstat 5.
Couture, Raymond; L'Ecuyer, Pierre (1997). «Distribution properties of Multiply-with-carry random number generators». Mathematics of Computation 66 (218): 591-607. doi:10.1090/S0025-5718-97-00827-2.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Section 7.1.2.B Multiply With Carry (MWC)». Numerical Recipes: The Art of Scientific Computing (3rd edición). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Archivado desde el original|urlarchivo= requiere |url= (ayuda) el 11 de agosto de 2011. Consultado el 18 de diciembre de 2014.

Datos: Q1952481