First things first:
~ This is my first question on StackOverflow.
~ I am a university student.
~ This is not my homework problem (I am doing this to increase my algorithmic thinking).
Here is my implementation, which keeps on returning wrong answers. I've tried running GDB, but was too inexperienced to make out where the algorithm was going wrong. Please help:
#include <iostream>
#include <cmath>
using namespace std;
int equalize(string &num1, string &num2){
int len1 = num1.length();
int len2 = num2.length();
if (len1 < len2){
for (int i = 0; i < len2 - len1; i++){
num1 = '0' + num1;
}
return len2;
} else{
for (int i = 0; i < len1 - len2; i++){
num2 = '0' + num2;
}
return len1;
}
}
string add(string num1, string num2){
string result;
int length = equalize(num1, num2);
int carryover = 0;
for (int i = length - 1; i >= 0; i--){
int a = num1[i] - '0';
int b = num2[i] - '0';
int sum = a + b + carryover;
carryover = sum / 10;
sum = sum % 10;
result = to_string(sum) + result;
}
if (carryover)
result = to_string(carryover) + result;
return result;
}
long karatsuba(string num1, string num2){
int n = equalize(num1, num2);
if (n == 0)
return 0;
else if (n == 1){
return (num1[0] - '0') * (num2[0] - '0');
} else{
int primary = n / 2;
int secondary = n - primary;
string A = num1.substr(0, primary);
string B = num1.substr(primary, secondary);
string C = num2.substr(0, primary);
string D = num2.substr(primary, secondary);
long AC = karatsuba(A, C);
long BD = karatsuba(B, D);
long ABCD = karatsuba(add(A, B), add(C, D));
return ((AC * pow(10, 2 * primary)) + ((ABCD - AC - BD) * pow(10, primary)) + (BD));
}
}
int main() {
string a = "111", b = "111";
cout << karatsuba(a, b);
return 0;
}
The answer returned is 441
which should ideally be 12321
.