C++ Implementations
Full Arbitrary-Precision Karatsuba (String-Based)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// ── Helpers ───────────────────────────────────────────────────────────
string addStr(string a, string b) {
// Elementary addition of two non-negative digit strings
int i = a.size()-1, j = b.size()-1, carry = 0;
string res;
while (i>=0 || j>=0 || carry) {
int s = carry;
if (i>=0) s += a[i--]-'0';
if (j>=0) s += b[j--]-'0';
res += char('0' + s%10);
carry = s/10;
}
reverse(res.begin(), res.end());
return res.empty() ? "0" : res;
}
string subStr(string a, string b) {
// a - b, assumes a >= b
int i=a.size()-1, j=b.size()-1, borrow=0;
string res;
while (i>=0) {
int d = (a[i--]-'0') - borrow - (j>=0 ? b[j--]-'0' : 0);
if (d < 0) { d += 10; borrow=1; } else borrow=0;
res += char('0'+d);
}
while (res.size()>1 && res.back()=='0') res.pop_back();
reverse(res.begin(), res.end());
return res;
}
string shift(string a, int zeros) { // multiply by 10^zeros
return a=="0" ? "0" : a + string(zeros,'0');
}
void pad(string &a, string &b) {
// Left-pad shorter string with '0' to equal length
while (a.size() < b.size()) a = "0"+a;
while (b.size() < a.size()) b = "0"+b;
}
// ── Karatsuba Core ────────────────────────────────────────────────────
string karatsuba(string x, string y) {
pad(x, y);
int n = x.size();
// Base case: single digit
if (n == 1)
return to_string((x[0]-'0') * (y[0]-'0'));
int m = n / 2; // split point
string a = x.substr(0, n-m); // high half of x
string b = x.substr(n-m); // low half of x
string c = y.substr(0, n-m); // high half of y
string d = y.substr(n-m); // low half of y
string z0 = karatsuba(a, c); // ac
string z2 = karatsuba(b, d); // bd
string z1 = karatsuba(addStr(a,b), addStr(c,d)); // (a+b)(c+d)
// ad+bc = z1 - z0 - z2
string mid = subStr(subStr(z1, z0), z2);
// Combine: z0*10^(2m) + mid*10^m + z2
string result = addStr(addStr(shift(z0,2*m), shift(mid,m)), z2);
// Remove leading zeros
size_t pos = result.find_first_not_of('0');
return (pos==string::npos) ? "0" : result.substr(pos);
}
int main() {
// Small example
cout << karatsuba("1234","5678") << "\n"; // 7006652
// Large numbers (e.g., 60-digit numbers)
string pi60 = "314159265358979323846264338327950288419716939937510";
string e60 = "271828182845904523536028747135266249775724709369995";
string big = karatsuba(pi60, e60);
cout << "Product length: " << big.size() << " digits\n";
cout << "First 20 digits: " << big.substr(0,20) << "...\n";
return 0;
}
Long Long Version (for numbers fitting in 64-bit integers)
#include <iostream>
#include <cmath>
using namespace std;
long long karatsuba(long long x, long long y) {
if (x < 10 || y < 10) return x * y; // base case
int n = max((int)log10(x)+1, (int)log10(y)+1);
long long m = (long long)pow(10, n/2);
long long a = x/m, b = x%m;
long long c = y/m, d = y%m;
long long z0 = karatsuba(a, c);
long long z2 = karatsuba(b, d);
long long z1 = karatsuba(a+b, c+d);
return z0*m*m + (z1-z0-z2)*m + z2;
}
int main() {
cout << karatsuba(1234, 5678) << "\n"; // 7006652
cout << karatsuba(99999, 99999) << "\n"; // 9999800001
return 0;
}