I've been trying to implement the Karatsuba multiplication algorithm in C++ for two large numbers of the same length. My code is behaving properly for smaller numbers, such as 3456*1492, but fails with large numbers such as those with 64-digits. It generally gets the first few digits correct but goes awry after that. I am using the Boost multiprecision library to handle the large integers.
My code is as follows:
cpp_int karatsuba(cpp_int n1, cpp_int n2) {
if (n1 < 10 || n2 < 10) {
return n1 * n2;
}
int len = countDigits(n1);
cpp_int a = n1 / cpp_int(pow(10, len/2));
cpp_int b = n1 % cpp_int(pow(10, len/2));
cpp_int c = n2 / cpp_int(pow(10, len/2));
cpp_int d = n2 % cpp_int(pow(10, len/2));
cpp_int sub1 = karatsuba(a, c);
cpp_int sub2 = karatsuba(b, d);
cpp_int sub3 = karatsuba(a+b, c+d) - sub1 - sub2;
return sub1 * cpp_int(pow(10, len)) + sub3 * cpp_int(pow(10, len/2)) + sub2;
}
I have compared my code to several implementations online and I haven't been able to find any significant differences that would affect the answer. Is there perhaps an issue with the precision of the cpp_int type or is there an issue in my code?
Thank you so much for your help!
I suspect one problem is that pow is returning a floating point representation which is being inaccurately converted into a cpp_int.
Using a multiprecision version of pow could help.
Also, len/2 rounds down, so when computing pow(10,len) this should instead be pow(10,(len/2)*2).