Karatsuba algorithm (C++ recipe) by Guillermo López

ActiveState Code (http://code.activestate.com/recipes/576827/)

/* Alumno: Guillermo López Leal 2IM1
 * 
 * Karatsuba algorith: fast multiplication of large integers.
 * 
 * Sorry for the comments in Spanish, but I think the code is very legible ;)
 */
#include <iostream>
#include <math .h>
 
using namespace std;
 
/*
 * Función Power(double x, int y)
 * calcula el número que resulta de calcular
 * x elevado a y. Se realiza por recursión.
 * Devuelve un tipo T, que se supone será
 * un número: int, double, float...
 *
 */
int Power(int x, int y) {
	if (y == 0)
		return (1);
	else if (y == 1)
		return(x);
	else
		return(x * Power(x, y-1));
}
 
/*
 * Función Digitos (T n, int &dig)
 * calcula el número de dígitos (dig) que tiene el número n, que
 * podría ser cualquier tipo de número: int, float, double...
 * Devuelve el número de dígitos (int).
 * He preferido cambiar la función para que devuelva el número
 * de dígitos en vez de mostrarlo por pantalla ya que en el algoritmo de
 * Karatsuba es necesario saber el número de dígitos de un número.
 *
 */
 
int Digitos (int n, int &dig) {
	if (n < 10)	return (dig+1);
	else {
		dig++;
		return(Digitos(n/10, dig));
	}
}
 
/*
 * Recibimos el número de dígitos que queremos ver como últimos
 * y el número, claro
 * Devolvemos el módulo de dividir el número entre la potencia de 10
 * elevado al número de dígitos:
 * e.g. sacar los últimos 3 dígitos de 3454567:
 * 3454567 % power(10, 3) -> 3454567 % 1000 -> 567
 *
 */
int ultimos(int digitos, int &numero) {
	return numero % Power(10, digitos);
}
 
/*
 * Al igual que con los últimos, devolvemos los n primeros "digitos" de "numero".
 * para ello usamos algo simple: dividimos el número entre la potencia de 10 elevado
 * al número de dígitos que queremos sacar.
 *
 */
int primeros(int digitos, int &numero) {
	return numero/Power(10, digitos);
}
 
/*
 * Algoritmo de Karatsuba. Multiplicación rápida de enteros largos
 * @param: int &u -> pasamos por referencia uno de los números a multiplicar.
 * @param: int &v -> pasamos por referencia el segundo número.
 */
int multiplica (int &u, int &v) {
	int dig1=0, dig2=0;
	//División en trozos iguales de los números. Tenemos que dividir según
	//el mayor de ambos entre 2: 3457689 -> 345 y 7689
	//							 3455 -> 0 y 3455
	int numDigitos = max(Digitos(u, dig1), Digitos(v, dig2));
	//Caso base, cuando se puede hacer una multiplicación directa (1 cifra)
	//En teoría si se lograba beneficio con números de más de 300 bits, se podría
	//sustituir ese 1 por 300.
	if (numDigitos < = 1) return u*v;
	//Número de dígitos redondeados HACIA ARRIBA para sacar la división.
	//e.g -> 9 dígitos de máximo -> sacamos los 5 últimos y después los 4 primeros
	//NO podemos sacar los 4.5 mayores y los 4.5 menores
	numDigitos = (numDigitos / 2) + (numDigitos % 2);
	//Vamos calculando los diferentes w, x, y, z…
	int w = primeros(numDigitos, u);
	int x = ultimos(numDigitos, u);
	int y = primeros(numDigitos, v);
	int z = ultimos(numDigitos, v);
	//Operaciones intermedias
	int p=multiplica(w, y);
	int q=multiplica(x, z);
	int wMasx = w + x;
	int zMasy = z + y;
	//Volvemos a llamar al algoritmo hasta que (como se ve arriba en el if) lleguemos al
	//caso base de n=numDigitos=1. Llamada recursiva
	int r=multiplica(wMasx, zMasy);
	// Salida final, usamos la función Power implementada arriba
	return Power(10, 2*numDigitos)*p+Power(10, numDigitos)*(r-p-q)+q;
}
 
//Funcion aleatoria para sacar números aleatorios menores que el parámetro x
int MiRandom(int x)
{
	int Numero=0;
	Numero=(rand()%x);
	return Numero;
}
 
int main () {
	//Inicializamos la semilla apuntando al tiempo
	srand(time(NULL));
	int numero=0;
	//Menor que 46340 -> raiz(max_int)=raiz(2147483647)...
	//Obviamente podría funcionar con más de 46340, pero podría producirse overflow.
	//Sólo ocurriría en el caso de que la semilla hiciera dos 46341 -> bum!!
	// Se podría poner hasta semilla 2147483647 si se tuviera la suerte que el random
	// fuera 1 y 2147483647
	//Además es que hemos limitado a "int", si hubiéramos puesto un valor más grande, como
	//unsigned long long int, tendríamos valores perfectos y muy grandes
	cout < < "Número máximo a multiplicar (menor que 46341, leer código fuente) :";
	cin >> numero;
	//Creamos dos enteros aleatorios máximo "numero"
	int num1 = MiRandom(numero);
	int num2 = MiRandom(numero);
	//Les mostramos
	cout < < "\nnum1=" << num1;
	cout << "\nnum2=" << num2;
	//Les multiplicamos!
	cout << "\nEl resultado del producto es: " << multiplica(num1, num2);
	return EXIT_SUCCESS;
}