1

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!

Arnav Garg
  • 33
  • 1
  • 7
  • What's the implementation of countDigits? – Jan Schultke May 25 '20 at 21:28
  • The numbers it is failing with are too large to fit in a `double`, but I am getting the same issues with `uint1024_t`. – Arnav Garg May 25 '20 at 21:31
  • `countDigits` repeatedly divides by 10 until the number is equal to 0 and counts the number of divisions. I have tested `countDigits` so I am confident the issue is not there. – Arnav Garg May 25 '20 at 21:32
  • Did you look at the Karatsuba in Boost.Multiprecision? https://github.com/boostorg/multiprecision/blob/develop/include/boost/multiprecision/cpp_int/multiply.hpp – user14717 May 25 '20 at 21:33
  • why to use `pow` inside multiplication? that is crazy and negates the Karatsuba complexity benefits as pow is higher operation (that also uses multiplication inside which would stack overflow if your Karatsuba was used btw.) and much slower ... use power of 2 base for splitting and bit operations (bit shifts,AND masking... ) instead. Also see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214). – Spektre May 26 '20 at 06:45

1 Answers1

2

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).

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • Switching to the multiprecision implementation of pow fixed the issue I was having with precision. Thank you so much! – Arnav Garg May 25 '20 at 21:58