Hi every one, I had implemented Karatsuba algorithm in C++, but I have been stuck for 2 days.
First problem is the function give incorrect answer, second problem is it oftens crash when run (runtime error). I try to debug but cannot understand how it's not work. I hope someone will help me out. I test all related functions of this function, everything work fine except Karatsuba function (I call it kmulrun).
I implement big integers in base 10^4 (so the product of to digits will fit well in int type, for maximum performance), I implement all core functions by the way that they will not return any value, instead, they use reference and constant reference to speed things up. The kmulrun function simply do recursive job, while the kmul function do the job of change both big integers to the length of 2^k (>= n) before pasing to kmulrun and after kmulrun finish the job, the kmul function delete all trailing zeroes in the result.
Here is my implementation of Karatsuba algorithm plus all related function:
typedef vector<int> bigint; // base 10000
// Utility functions
void del0(bigint &res) {
// delete trailing zeroes at begining
int n = res.size() - 1;
int i = 0;
for (; i < n; ++i) {
if (res[i] != 0) {
break;
}
}
res.erase(res.begin(), res.begin() + i);
}
void fromlonglong(bigint &res, long long n) {
// convert a long long int to bignum
if (n < 1) {
res.clear();
res.push_back(0);
return;
}
long long tn = n;
int t = 0;
while (tn != 0) {
tn /= 10000;
++t;
}
res.resize(t);
int i = 0;
while (n != 0) {
res[t - 1 - i++] = n % 10000;
n /= 10000;
}
}
void ncopy(bigint &res, const bigint &source, const int l, const int r) {
// copy all members in range [l, r] from source to res
res.clear();
for (int i = l; i <= r; ++i) {
res.push_back(source[i]);
}
}
// Core functions
int cmp(const bigint &x, const bigint &y) {
// compare two bigints
int nx = x.size();
int ny = y.size();
if (nx != ny) {
return nx > ny ? 1 : -1;
}
int n = x.size();
for (int i = 0; i < n; ++i) {
if (x[i] != y[i]) {
return x[i] > y[i] ? 1 : -1;
}
}
return 0;
}
void exp(bigint &res, const int n) {
// exp(res, n) = res * 10 ^ n
for (int i = 0; i < n; ++i) {
res.push_back(0);
}
}
void add(bigint &res, const bigint &x, const bigint &y) {
// below 1s if input size smaller or equal to 1 billion
int nx = x.size();
int ny = y.size();
int n = nx > ny ? nx : ny;
res.resize(n);
int r = 0;
if (nx >= ny) {
int k = nx - ny;
for (int i = n - 1; i >= k; --i) {
int t = x[i] + y[i - k] + r;
res[i] = t % 10000;
r = t / 10000;
}
for (int i = k - 1; i >= 0; --i) {
int t = x[i] + r;
res[i] = t % 10000;
r = t / 10000;
}
}
else {
int k = ny - nx;
for (int i = n - 1; i >= k; --i) {
int t = y[i] + x[i - k] + r;
res[i] = t % 10000;
r = t / 10000;
}
for (int i = k - 1; i >= 0; --i) {
int t = y[i] + r;
res[i] = t % 10000;
r = t / 10000;
}
}
if (r != 0) {
res.insert(res.begin(), r);
}
}
void sub(bigint &res, const bigint &x, const bigint &y) {
// below 1s if input size smaller or equal to 1 billion
int nx = x.size();
int ny = y.size();
int c = cmp(x, y);
if (c == 0) {
res.clear();
res.push_back(0);
return;
}
int n = nx > ny ? nx : ny;
res.resize(n);
int r = 0;
if (c == 1) {
int k = nx - ny;
for (int i = n - 1; i >= k; --i) {
int t = x[i] + 10000 - y[i - k] - r;
res[i] = t % 10000;
r = x[i] < y[i - k] + r ? 1 : 0;
}
for (int i = k - 1; i >= 0; --i) {
int t = x[i] - r;
res[i] = t % 10000;
r = x[i] < r ? 1 : 0;
}
}
else {
int k = ny - nx;
for (int i = n - 1; i >= k; --i) {
int t = y[i] + 10000 - x[i - k] - r;
res[i] = t % 10000;
r = y[i] < x[i - k] + r ? 1 : 0;
}
for (int i = k - 1; i >= 0; --i) {
int t = y[i] - r;
res[i] = t % 10000;
r = y[i] < r ? 1 : 0;
}
}
del0(res);
}
// Karatsuba multiplication functions
void kmulrun(bigint &res, const bigint &x, const bigint &y) {
int n = x.size();
if (n == 2) {
long long t = (long long)(x[0] * 10000 + x[1]) * (y[0] * 10000 + y[1]);
fromlonglong(res, t);
return;
}
int hn = n / 2;
bigint a, b, c, d, u, v, w, t1, t2, t3, t4, t5;
ncopy(a, x, 0, hn - 1);
ncopy(b, x, hn, n - 1);
ncopy(c, y, 0, hn - 1);
ncopy(d, y, hn, n - 1);
kmulrun(u, a, c); // u = a * c
kmulrun(v, b, d); // v = b * d
add(t1, a, b); // t1 = a + b
add(t2, c, d); // t2 = c + d
kmulrun(t3, t1, t2); // t3 = t1 * t2 = (a + b) * (c + d)
sub(t4, t3, u); // t4 = t3 - u = (a + b) * (c + d) - u
sub(w, t4, v); // w = t4 - v = (a + b) * (c + d) - u - v
exp(u, n); // u = u * B ^ n
exp(w, hn); // w = w * B ^ (n / 2)
add(t5, w, u); // t5 = u + w
add(res, t5, v); // res = t5 + v = u + w + v
}
void kmulins0(bigint &x, bigint &y) {
int nx = x.size();
int ny = y.size();
int n = nx > ny ? nx : ny;
int t = 1;
while (t < n) {
t *= 2;
}
x.insert(x.begin(), t - nx, 0);
y.insert(y.begin(), t - ny, 0);
wl(x);
wl(y);
}
void kmul(bigint &res, const bigint &x, const bigint &y) {
bigint tx = x;
bigint ty = y;
kmulins0(tx, ty);
if (x.size() == 1) {
fromint(res, x[0] * y[0]);
return;
}
kmulrun(res, tx, ty);
del0(res);
}
// bonus, my grade school algorithm implementation
// works well, but runtime will be greater than 1 second if
// the the integers has more than 40 000 digits (count int base 10)
void mul(bigint &res, const bigint &x, const bigint &y) {
int nx = x.size();
int ny = y.size();
res.clear();
res.push_back(0);
for (int i = nx - 1; i >= 0; --i) {
if (x[i] == 0) {
continue;
}
bigint temp(ny);
int r = 0;
for (int j = ny - 1; j >= 0; --j) {
int t = x[i] * y[j] + r;
temp[j] = t % 10000;
r = t / 10000;
}
if (r != 0) {
temp.insert(temp.begin(), r);
}
exp(temp, nx - i - 1);
add(res, res, temp);
}
}
// My spec
CPU Intel Core i5 5500 2.2 GHz