Simple C++ Karatsuba implementation.

karatsuba.cc

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> using V = vector<T>;

string bigint_to_str(const V<char>& c)
{
    string s = "";
    for (int i = c.size()-1; i >= 0; --i) {
        s += c[i] + '0';
    }
    if (s.empty()) return "0";
    return s;
}

V<char> str_to_bigint(const string& s)
{
    V<char> c(s.size());
    for (int i = 0; i < s.size(); ++i) {
        c[c.size()-1-i] = s[i] - '0';
    }
    return c;
}

void clear_leading_zeros(V<char>& c)
{
    while (c.size() > 1 and c.back() == 0) {
        c.pop_back();
    }
}

V<char> left_shift(const V<char>& c, int n)
{
    V<char> r(c.size()+n, 0);
    for (int i = 0; i < c.size(); ++i) {
        r[i+n] = c[i];
    }
    return r;
}

V<char> operator+(const V<char>& a, const V<char>& b)
{
    int n = a.size();
    int m = b.size();
    int k = max(n, m) + 1;
    V<char> c(k, 0);
    for (int i = 0; i < k; ++i) {
        if (i < n) c[i] += a[i];
        if (i < m) c[i] += b[i];
        if (c[i] >= 10) {
            c[i] -= 10;
            ++c[i+1];
        }
    }
    clear_leading_zeros(c);
    return c;
}

V<char> operator*(const V<char>& a, const V<char>& b)
{
    int n = a.size();
    int m = b.size();
    if (n + m + 1 <= 17) { // compute using long long
        ll A = stoll(bigint_to_str(a));
        ll B = stoll(bigint_to_str(b));
        return str_to_bigint(to_string(A * B));
    }
    // Karatsuba
    V<char> a1(a.begin()+n/2, a.end());
    V<char> a2(a.begin(), a.begin()+n/2);
    V<char> b1(b.begin()+m/2, b.end());
    V<char> b2(b.begin(), b.begin()+m/2);
    V<char> c1 = a1 * b1;
    V<char> c2 = a1 * b2;
    V<char> c3 = a2 * b1;
    V<char> c4 = a2 * b2;
    V<char> c = left_shift(c1, n/2+m/2) + left_shift(c2, n/2) + left_shift(c3, m/2) + c4;
    return c;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string sa, sb;
    cin >> sa >> sb;
    V<char> a = str_to_bigint(sa);
    V<char> b = str_to_bigint(sb);
    cout << bigint_to_str(a*b) << endl;
}