Aritmética de precisión arbitraria

La aritmética de precisión arbitraria (arbitrary-precision arithmetic), también conocida como “bignum” o simplemente “aritmética larga”, es un conjunto de estructuras de datos y algoritmos que permite procesar números mucho mayores de los que caben en los tipos de datos estándar. Aquí se presentan varios tipos de aritmética de precisión arbitraria.

Aritmética larga clásica de enteros

La idea principal es que el número se almacena como un arreglo de sus “dígitos” en alguna base. Varias de las bases más usadas son la decimal, potencias de diez ( $10^4$ o $10^9$ ) y la binaria.

Las operaciones sobre números en esta forma se realizan con los algoritmos “escolares” de suma, resta, multiplicación y división en columna. También es posible usar algoritmos de multiplicación rápida: la transformada rápida de Fourier y el algoritmo de Karatsuba.

Aquí describimos la aritmética larga solo para enteros no negativos. Para extender los algoritmos a enteros negativos hay que introducir y mantener un flag adicional de “número negativo”, o usar la representación en complemento a dos.

Estructura de datos

Almacenaremos los números como un vector<int>, en el que cada elemento es un solo “dígito” del número.


typedef vector<int> lnum;

Para mejorar el rendimiento usaremos $10^9$ como base, de modo que cada “dígito” del número largo contenga 9 dígitos decimales a la vez.


const int base = 1000*1000*1000;

Los dígitos se almacenarán en orden de menos a más significativo. Todas las operaciones se implementarán de modo que, después de cada una, el resultado no tenga ceros a la izquierda, siempre que los operandos tampoco los tuvieran. Toda operación que pueda producir un número con ceros a la izquierda debe ir seguida del código que los elimine. Nótese que en esta representación hay dos notaciones válidas para el número cero: un vector vacío y un vector con un único dígito cero.

Salida

Imprimir el entero largo es la operación más fácil. Primero imprimimos el último elemento del vector (o 0 si el vector está vacío), seguido del resto de los elementos rellenados con ceros a la izquierda si hace falta para que tengan exactamente 9 dígitos.


printf ("%d", a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i)
	printf ("%09d", a[i]);

Nótese que casteamos a.size() a entero para evitar el underflow de enteros sin signo si el vector contiene menos de 2 elementos.

Entrada

Para leer un entero largo, leemos su notación en un string y luego la convertimos a “dígitos”:


for (int i=(int)s.length(); i>0; i-=9)
	if (i < 9)
		a.push_back (atoi (s.substr (0, i).c_str()));
	else
		a.push_back (atoi (s.substr (i-9, 9).c_str()));

Si usamos un arreglo de char en lugar de un string, el código será aún más corto:


for (int i=(int)strlen(s); i>0; i-=9) {
	s[i] = 0;
	a.push_back (atoi (i>=9 ? s+i-9 : s));
}

Si la entrada puede contener ceros a la izquierda, se pueden eliminar así:


while (a.size() > 1 && a.back() == 0)
	a.pop_back();

Suma

Incrementar el entero largo $a$ en $b$ y guardar el resultado en $a$ :


int carry = 0;
for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) {
	if (i == a.size())
		a.push_back (0);
	a[i] += carry + (i < b.size() ? b[i] : 0);
	carry = a[i] >= base;
	if (carry)  a[i] -= base;
}

Resta

Decrementar el entero largo $a$ en $b$ ( $a \ge b$ ) y guardar el resultado en $a$ :


int carry = 0;
for (size_t i=0; i<b.size() || carry; ++i) {
	a[i] -= carry + (i < b.size() ? b[i] : 0);
	carry = a[i] < 0;
	if (carry)  a[i] += base;
}
while (a.size() > 1 && a.back() == 0)
	a.pop_back();

Nótese que después de restar eliminamos los ceros a la izquierda para mantener la premisa de que nuestros enteros largos no tienen ceros a la izquierda.

Multiplicación por un entero corto

Multiplicar el entero largo $a$ por el entero corto $b$ ( $b < base$ ) y guardar el resultado en $a$ :


int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i) {
	if (i == a.size())
		a.push_back (0);
	long long cur = carry + a[i] * 1ll * b;
	a[i] = int (cur % base);
	carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
	a.pop_back();

Optimización adicional: si el tiempo de ejecución es extremadamente importante, se puede intentar reemplazar dos divisiones por una, calculando solo el resultado entero de la división (variable carry) y usándolo después para obtener el módulo mediante una multiplicación. Esto suele hacer el código más rápido, aunque no de forma dramática.

Multiplicación por un entero largo

Multiplicar los enteros largos $a$ y $b$ y guardar el resultado en $c$ :


lnum c (a.size()+b.size());
for (size_t i=0; i<a.size(); ++i)
	for (int j=0, carry=0; j<(int)b.size() || carry; ++j) {
		long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
		c[i+j] = int (cur % base);
		carry = int (cur / base);
	}
while (c.size() > 1 && c.back() == 0)
	c.pop_back();

División por un entero corto

Dividir el entero largo $a$ por el entero corto $b$ ( $b < base$ ), guardar el resultado entero en $a$ y el resto en carry:


int carry = 0;
for (int i=(int)a.size()-1; i>=0; --i) {
	long long cur = a[i] + carry * 1ll * base;
	a[i] = int (cur / b);
	carry = int (cur % b);
}
while (a.size() > 1 && a.back() == 0)
	a.pop_back();

Aritmética de enteros largos para la representación por factorización

La idea es almacenar el entero como su factorización, es decir, las potencias de los primos que lo dividen.

Este enfoque es muy fácil de implementar y permite hacer multiplicación y división con facilidad (asintóticamente más rápido que el método clásico), pero no suma ni resta. También es muy eficiente en memoria comparado con el enfoque clásico.

Este método se usa a menudo para cálculos módulo un número no primo $M$ ; en ese caso un número se almacena como las potencias de los divisores de $M$ que dividen al número, más el resto módulo $M$ .

Aritmética de enteros largos en módulos primos (algoritmo de Garner)

La idea es elegir un conjunto de números primos (típicamente lo bastante pequeños como para caber en un tipo entero estándar) y almacenar un entero como un vector de restos de la división del entero por cada uno de esos primos.

El teorema chino del resto afirma que esta representación basta para restaurar de forma única cualquier número de 0 al producto de estos primos menos uno. El algoritmo de Garner permite restaurar el número desde esa representación a un entero normal.

Este método permite ahorrar memoria respecto del enfoque clásico (aunque el ahorro no es tan dramático como en la representación por factorización). Además, permite realizar suma, resta y multiplicación rápidas en un tiempo proporcional a la cantidad de números primos usados como módulos (véase el artículo del Teorema Chino del Resto para la implementación).

El costo es que convertir el entero de vuelta a la forma normal es bastante laborioso y requiere implementar aritmética clásica de precisión arbitraria con multiplicación. Además, este método no soporta división.

Aritmética de precisión arbitraria fraccionaria

Las fracciones aparecen en los concursos de programación con menos frecuencia que los enteros, y la aritmética larga es mucho más engorrosa de implementar para fracciones, así que los concursos solo incluyen un subconjunto pequeño de aritmética larga fraccionaria.

Aritmética en fracciones irreducibles

Un número se representa como una fracción irreducible $\frac{a}{b}$ , donde $a$ y $b$ son enteros. Todas las operaciones sobre fracciones se pueden representar como operaciones sobre los numeradores y denominadores enteros de esas fracciones. Por lo general esto requiere usar aritmética clásica de precisión arbitraria para almacenar numerador y denominador, pero a veces basta un tipo entero nativo de 64 bits.

Guardar la posición del punto flotante como un tipo separado

A veces un problema exige manejar números muy pequeños o muy grandes sin permitir overflow ni underflow. El tipo nativo double usa 8-10 bytes y admite valores del exponente en el rango $[-308; 308]$ , lo que a veces puede no ser suficiente.

El enfoque es muy simple: se usa una variable entera separada para almacenar el valor del exponente, y después de cada operación el número de punto flotante se normaliza, es decir, se lo devuelve al intervalo $[0.1; 1)$ ajustando el exponente en consecuencia.

Cuando se multiplican o dividen dos de esos números, hay que sumar o restar sus exponentes, respectivamente. Cuando se suman o restan, primero hay que llevarlos a un exponente común multiplicando uno de ellos por 10 elevado a la diferencia de los valores de los exponentes.

Como nota final, la base del exponente no tiene que ser 10. Según la representación interna de los números de punto flotante, lo más razonable es usar 2 como base del exponente.