Multiplicación con acarreo
# 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^{60}$ 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

Una secuencia MWC está basada en un módulo de aritmética en base b, usualmente b = $2^{32},$ dado que dicho módulo en base b es automático en muchas computadoras. Sin embargo, a veces es usada una base b = $2^{32}$ − 1, porque la aritmética para módulos $2^{32}$ − 1 requiere solamente un ajuste simple hacia $2^{32},$ y la teoría para las secuencia MWC basadas en módulos $2^{32}$ presenta algunas dificultades muy molestas que pueden ser evitadas usando b = $2^{32}$ − 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_0,$ $x_1,$ $x_2,...,$ $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^{32}$ no puede ser una raíz primitiva de p = $ab^r$ − 1. Por consiguiente no hay generadores MWC en base $2^{32}$ que presentan el período máximo posible, una de las dificultades que el uso de b = $2^{32}$ − 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

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^{32}.$ Si a mod 8 es 1 o 5 y c es impar, la secuencia congruente resultante base $2^{32}$ tendrá un período $2^{32}.$

Un generador lag-1 de multiplicación con acarreo nos permite hacer el período aproximadamente $2^{63}$ 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^{32}$ en el grupo multiplicativo de residuales módulo ab − 1, o sea, en menor n tal que $b^n$ = 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^{63},$ 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^{16}$ | $2^{15}−50$ = 32,718 | 1,072,103,423 |
| 16 | $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 | 170,141,183,460,469,224,887,945,252,369,640,456,191 |
| 128 | $2^{128}$ | $2^{128}−10,408$ | $2^{127}(2^{128}−10,408)−1$ |
| 256 | $2^{256}$ | $2^{256}−9166$ | $2^{255}(2^{256}−9166)−1$ |
| 512 | $2^{512}$ | $2^{512}−150,736$ | $2^{511}(2^{512}−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^{16}$ | $2^{15}−29$ = 32,739 | 1,072,791,551 |
| 16 | $2^{16}$ | $2^{16}−22$ = 65,514 | 2,146,762,751 |
| 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 |
| 63 | $2^{64}$ | $2^{63}−140$ = 9,223,372,036,854,775,668 | 85,070,591,730,234,614,574,571,566,698,273,439,743 |
| 64 | $2^{64}$ | $2^{64}−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_0$ meramente rota el ciclo de x's.

## Generadores de Multiplicación con Acarreo Complementaria

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_0,$ $x_1,$ $x_2,...,$ $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^{32},$ 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^{32762},$ acerca de $10^{9867}$ para estos tres as: 109111 o 108798 o 108517.

Con b = $2^{32}$ y a = 3636507990, p = $ab^{1359}$ − 1 un primo seguro, entonces la secuencia MWC basada en esa a tiene período 3636507990$\cdot$$2^{43487}$ $\approx$$10^{13101}.$

Con b = $2^{32},$ un CMWC RNG con período récord cercano puede basarse en el primo p = $15455296b^{42658}$ + 1. El orden de b para ese primo es $241489*2^{1365056},$ cerca de $10^{410928}.$

## Implementación

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}$.

