Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple C++ Karatsuba implementation.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment