I'm trying to implement a recursive Karatsuba algorithm. I successfully coded a recursive algorithm for multiplication but it calculates ad and bc. However, for this program, I've tried noting down each intermediate value namely ac, bd, total, sum. Many values don't turn up as the expected value. I can't figure out where my code is getting messed up. I'm still an amateur programmer and I've spent already several hours trying to debug but now I have no choice but to post my large code here:
#include <iostream>
using namespace std;
int approxLog(int n, int b) {
return !(n/b < 1) ? 1+approxLog(n/b, b) : 1;
}
int power(int b, int e) {
return (e < 1) ? 1 : b*power(b, e-1);
}
int odd1(int n) {
if(n%2 != 0)
return n-1;
else
return n;
}
int odd2(int n) {
if(n%2 == 0)
return n/2;
else
return n/2 + 1;
}
void num_split (int num, int d, int *a, int *b) {
int i = 1, tmp = 0, j = 1, k = 0;
while (i <= d/2) {
tmp += (num%10)*power(10, i-1);
num /= 10;
i++;
}
*b = tmp;
tmp = 0;
while (i <= d) {
tmp += (num%10)*power(10, j-1);
num /= 10;
i++;
j++;
}
*a = tmp;
tmp = 0;
}
long long int multiply(int x, int y, int n) {
int a = 0, b = 0, c = 0, d = 0;
int ac = 0, bd = 0, total = 0, sum = 0;
int *ptr_a = &a;
int *ptr_b = &b;
int *ptr_c = &c;
int *ptr_d = &d;
num_split(x, n, ptr_a, ptr_b);
num_split(y, n, ptr_c, ptr_d);
if((x < 10) || (y < 10)) {
return x*y;
}
else {
ac = multiply(a, c, odd2(n));
bd = multiply(b, d, n/2);
total = multiply((a+b), (c+d), odd2(n));
// cout << total << endl;
sum = total - ac - bd;
return power(10, odd1(n))*ac + power(10, n/2))*sum + bd;
}
}
int main() {
int x = 1234, y = 1234;
int n = approxLog(x, 10);
long long int product = multiply(x, y, n);
cout << product << endl;
return 0;
}
The problem is that in each recursion, you should take the approx. log of the the bigger of x and y. So the following alteration in your code would fix the problem (notice the commented out portions too!):
long long int multiply(int x, int y)//, int n)
{
int a = 0, b = 0, c = 0, d = 0;
int ac = 0, bd = 0, total = 0, sum = 0;
int *ptr_a = &a;
int *ptr_b = &b;
int *ptr_c = &c;
int *ptr_d = &d;
int n = (x>y)?approxLog(x, 10):approxLog(y, 10);
num_split(x, n, ptr_a, ptr_b);
num_split(y, n, ptr_c, ptr_d);
if((x < 10) || (y < 10)) {
return x*y;
}
else {
ac = multiply(a, c);//, odd2(n));
bd = multiply(b, d);//, n/2);
total = multiply((a+b), (c+d));//, odd2(n));
cout << total << endl;
sum = total - ac - bd;
return power(10, odd1(n))*ac + power(10, (n/2))*sum + bd;
}
}
int main() {
int x = 134546, y = 1234;
//int n = approxLog(x, 10);
long long int product = multiply(x, y);//, n);
cout<<"Karatsuba: "<<product<<endl;
cout<<"Normal: "<<x*y<<endl;
return 0;
}