Por razones de clase, me tuve que ver en el apuro de programar un algoritmo de multiplicación rápida de enteros largos. Dimos algo de teoría en clase, pero necesitábamos programarlo mediante recursión. Vimos cómo era más eficaz frente a la multiplicación normal (la que nos enseñan en las escuelas, de multiplicar uno a uno y en cada iteración aumentar la sangría). En concreto el orden de la multiplicación de toda la vida es de O(n²), mientras que el de Karatsuba es del orden de O(n^1.59). Esta ligera mejoría se nota sobre todo en multiplicaciones de números de más de 300 bits.

Y ¿para qué cojones queremos multiplicar enteros de más de 300bits? Criptografía. El cifrado de los datos se basan en la multiplicación de dos números enteros muy largos y primos, por lo que su factorización es muy muy costosa.

En fin, que evitando matemáticas y demás tonterías variadas, el código de Karatsuba en C++ añadiendo las funciones necesarias para que funcione (sacado de uno en Java) queda en:

/* Alumno: Guillermo López Leal 2IM1
 * Compilador usado: GCC 4.0 en MacOS 10.5, pero debería funcionar en
 * cualquier Linux con su correspondiente configuración o incluso
 * en Windows bajo cygwin y mingw.
 *
 */
#include 
#include 

 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;
}

Sigue leyendo →