Karatsuba

Karatsuba.cpp

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

class Karatsuba {
private:
    // Remove leading zeros
    static string stripZeros(const string &num) {
        size_t pos = num.find_first_not_of('0');
        if (pos == string::npos) return "0";
        return num.substr(pos);
    }

    // Adds two numbers as strings
    static string addStrings(const string &a, const string &b) {
        string result = "";
        int carry = 0;
        int i = a.size() - 1, j = b.size() - 1;
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            result.push_back(sum % 10 + '0');
            carry = sum / 10;
        }
        reverse(result.begin(), result.end());
        return stripZeros(result);
    }

    // Subtract b from a (a >= b)
    static string subtractStrings(const string &a, const string &b) {
        string result = "";
        int borrow = 0;
        int i = a.size() - 1, j = b.size() - 1;
        while (i >= 0) {
            int diff = (a[i] - '0') - borrow - (j >= 0 ? (b[j] - '0') : 0);
            if (diff < 0) {
                diff += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }
            result.push_back(diff + '0');
            i--; j--;
        }
        reverse(result.begin(), result.end());
        return stripZeros(result);
    }

    // Multiply by 10^n (append zeros)
    static string shiftLeft(const string &num, int n) {
        return (num == "0") ? "0" : num + string(n, '0');
    }

public:
    // Recursive Karatsuba multiplication
    static string multiply(const string &x, const string &y) {
        string a = stripZeros(x), b = stripZeros(y);

        if (a.size() == 1 && b.size() == 1) {
            int prod = (a[0] - '0') * (b[0] - '0');
            return to_string(prod);
        }

        int n = max(a.size(), b.size());
        if (n % 2 != 0) n++; // make even length
        while (a.size() < n) a = "0" + a;
        while (b.size() < n) b = "0" + b;

        int m = n / 2;
        string a1 = a.substr(0, n - m);
        string a0 = a.substr(n - m);
        string b1 = b.substr(0, n - m);
        string b0 = b.substr(n - m);

        string z0 = multiply(a0, b0);
        string z2 = multiply(a1, b1);
        string z1 = subtractStrings(subtractStrings(multiply(addStrings(a1, a0), addStrings(b1, b0)), z2), z0);

        string result = addStrings(addStrings(shiftLeft(z2, 2 * m), shiftLeft(z1, m)), z0);
        return stripZeros(result);
    }
};


int main() {
    string x = "12345678";
    string y = "87654321";

    cout << "Multiplicando " << x << " x " << y << " ..." << endl;
    string result = Karatsuba::multiply(x, y);
    cout << "Resultado: " << result << endl;

    return 0;
}