DevJourney · code I wrote while learning
main.cpp
2.1 KB#include <iostream>
#include <string>
using namespace std;
string trim(const string &s)
{
int i = 0;
while (i < s.size() && s[i] == '0')
i++;
if (i == s.size())
return "0";
return s.substr(i);
}
string add(string a, string b)
{
if (a.size() < b.size())
swap(a, b);
int carry = 0;
string res = "";
int i = a.size() - 1;
int 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';
res = char('0' + sum % 10) + res;
carry = sum / 10;
}
return trim(res);
}
string sub(string a, string b) // assume a >= b
{
int borrow = 0;
string res = "";
int i = a.size() - 1;
int j = b.size() - 1;
while (i >= 0)
{
int diff = (a[i] - '0') - borrow;
if (j >= 0)
diff -= (b[j] - '0');
if (diff < 0)
{
diff += 10;
borrow = 1;
}
else
borrow = 0;
res = char('0' + diff) + res;
i--;
j--;
}
return trim(res);
}
string shift(string s, int k)
{
if (s == "0")
return s;
return s + string(k, '0');
}
string karatsuba(string x, string y)
{
x = trim(x);
y = trim(y);
if (x == "0" || y == "0")
return "0";
if (x.size() == 1 && y.size() == 1)
{
int p = (x[0] - '0') * (y[0] - '0');
return to_string(p);
}
int n = max(x.size(), y.size());
if (n % 2)
n++;
while (x.size() < n)
x = "0" + x;
while (y.size() < n)
y = "0" + y;
int m = n / 2;
string a = x.substr(0, n - m);
string b = x.substr(n - m);
string c = y.substr(0, n - m);
string d = y.substr(n - m);
string z2 = karatsuba(a, c);
string z0 = karatsuba(b, d);
string z1 = karatsuba(add(a, b), add(c, d));
string mid = sub(sub(z1, z2), z0);
string res = add(add(shift(z2, 2 * m), shift(mid, m)), z0);
return trim(res);
}
int main()
{
string a, b;
cin >> a >> b;
cout << karatsuba(a, b) << endl;
return 0;
}