Karatsuba Integer Multiplication failing with segmentation fault

Question

As I run the program, it crashes with segmentation fault. Also, when I debug the code in codeblocks IDE, I am unable to debug it as well. The program crashes even before debugging begins. I am not able to understand the problem. Any help would be appreciated. Thanks!!

#include <iostream>
#include <math.h>
#include <string>
using namespace std;

// Method to make strings of equal length
int makeEqualLength(string& fnum,string& snum){
    int l1 = fnum.length();
    int l2 = snum.length();
    if(l1>l2){
        int d = l1-l2;
        while(d>0){
            snum  = '0' + snum;
            d--;
        }
        return l1;
    }
    else if(l2>l1){
        int d = l2-l1;
        while(d>0){
            fnum  = '0' + fnum;
            d--;
        }
        return l2;
    }
    else
        return l1;
}

int singleDigitMultiplication(string& fnum,string& snum){
    return ((fnum[0] -'0')*(snum[0] -'0'));
}

string addStrings(string& s1,string& s2){
  int length = makeEqualLength(s1,s2);
  int carry = 0;
  string result;
  for(int i=length-1;i>=0;i--){
    int fd = s1[i]-'0';
    int sd = s2[i]-'0';
    int sum = (fd+sd+carry)%10+'0';
    carry = (fd+sd+carry)/10;
    result = (char)sum + result;
  }
  result = (char)carry + result;
  return result;
}

long int multiplyByKaratsubaMethod(string fnum,string snum){

    int length = makeEqualLength(fnum,snum);
    if(length==0) return 0;
    if(length==1) return singleDigitMultiplication(fnum,snum);

    int fh = length/2;
    int sh = length - fh;

    string Xl = fnum.substr(0,fh);
    string Xr = fnum.substr(fh,sh);
    string Yl = snum.substr(0,fh);
    string Yr = snum.substr(fh,sh);

    long int P1 = multiplyByKaratsubaMethod(Xl,Yl);
    long int P3 = multiplyByKaratsubaMethod(Xr,Yr);
    long int P2 = multiplyByKaratsubaMethod(addStrings(Xl,Xr),addStrings(Yl,Yr)) - P1-P3;

    return (P1*pow(10,length) + P2*pow(10,length/2) + P3);
}


int main()
{
    string firstNum = "62";
    string secondNum = "465";
    long int result = multiplyByKaratsubaMethod(firstNum,secondNum);
    cout << result << endl;
    return 0;
}

Answer 1

There are three serious issues in your code:

1. result = (char)carry + result; does not work.
   The carry has a value between 0 (0 * 0) and 8 (9 * 9). It has to be converted to the corresponding ASCII value:
   result = (char)(carry + '0') + result;.

2. This leads to the next issue: The carry is even inserted if it is 0. There is an if statement missing:
   if (carry/* != 0*/) result = (char)(carry + '0') + result;.

3. After fixing the first two issues and testing again, the stack overflow still occurs. So, I compared your algorithm with another I found by google:
   Divide and Conquer | Set 4 (Karatsuba algorithm for fast multiplication)
   (and possibly was your origin because it's looking very similar). Without digging deeper, I fixed what looked like a simple transfer mistake:
   return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3;
   (I replaced length by 2 * sh and length/2 by sh like I saw it in the googled code.) This became obvious for me seeing in the debugger that length can have odd values so that sh and length/2 are distinct values.

Afterwards, your program became working.

I changed the main() function to test it a little bit harder:

#include <cmath>
#include <iostream>
#include <string>

using namespace std;

string intToStr(int i)
{
  string text;
  do {
    text.insert(0, 1, i % 10 + '0');
    i /= 10;
  } while (i);
  return text;
}

// Method to make strings of equal length
int makeEqualLength(string &fnum, string &snum)
{
  int l1 = (int)fnum.length();
  int l2 = (int)snum.length();
  return l1 < l2
    ? (fnum.insert(0, l2 - l1, '0'), l2)
    : (snum.insert(0, l1 - l2, '0'), l1);
}

int singleDigitMultiplication(const string& fnum, const string& snum)
{
  return ((fnum[0] - '0') * (snum[0] - '0'));
}

string addStrings(string& s1, string& s2)
{
  int length = makeEqualLength(s1, s2);
  int carry = 0;
  string result;
  for (int i = length - 1; i >= 0; --i) {
    int fd = s1[i] - '0';
    int sd = s2[i] - '0';
    int sum = (fd + sd + carry) % 10 + '0';
    carry = (fd + sd + carry) / 10;
    result.insert(0, 1, (char)sum);
  }
  if (carry) result.insert(0, 1, (char)(carry + '0'));
  return result;
}

long int multiplyByKaratsubaMethod(string fnum, string snum)
{
  int length = makeEqualLength(fnum, snum);
  if (length == 0) return 0;
  if (length == 1) return singleDigitMultiplication(fnum, snum);

  int fh = length / 2;
  int sh = length - fh;

  string Xl = fnum.substr(0, fh);
  string Xr = fnum.substr(fh, sh);
  string Yl = snum.substr(0, fh);
  string Yr = snum.substr(fh, sh);

  long int P1 = multiplyByKaratsubaMethod(Xl, Yl);
  long int P3 = multiplyByKaratsubaMethod(Xr, Yr);
  long int P2
    = multiplyByKaratsubaMethod(addStrings(Xl, Xr), addStrings(Yl, Yr))
    - P1 - P3;
  return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3;
}

int main()
{
  int nErrors = 0;
  for (int i = 0; i < 1000; i += 3) {
    for (int j = 0; j < 1000; j += 3) {
      long int result
        = multiplyByKaratsubaMethod(intToStr(i), intToStr(j));
      bool ok = result == i * j;
      cout << i << " * " << j << " = " << result
        << (ok ? " OK." : " ERROR!") << endl;
      nErrors += !ok;
    }
  }
  cout << nErrors << " error(s)." << endl;
  return 0;
}

Notes about changes I've made:

1. Concerning std library: Please, don't mix headers with ".h" and without. Every header of std library is available in "non-suffix-flavor". (The header with ".h" are either C header or old-fashioned.) Headers of C library have been adapted to C++. They have the old name with prefix "c" and without suffix ".h".
   Thus, I replaced #include <math.h> by #include <cmath>.

2. I couldn't resist to make makeEqualLength() a little bit shorter.

3. Please, note, that a lot of methods in std use std::size_t instead of int or unsigned. std::size_t has appropriate width to do array subscript and pointer arithmetic i.e it has "machine word width". I believed a long time that int and unsigned should have "machine word width" also and didn't care about size_t. When we changed in Visual Studio from x86 (32 bits) to x64 (64 bits), I learnt the hard way that I had been very wrong: std::size_t is 64 bits now but int and unsigned are still 32 bits. (MS VC++ is not an exception. Other compiler vendors (but not all) do it the same way.)
   I inserted some C type casts to remove the warnings from compiler output. Such casts to remove warnings (regardless you use C casts or better the C++ casts) should always be used with care and should be understood as confirmation: Dear compiler. I see you have concerns but I (believe to) know and assure you that it should work fine.

4. I'm not sure about your intention to use long int in some places. (Probably, you transferred this code from original source without caring about.) As your surely know, the actual size of all int types may differ to match best performance of the target platform. I'm working on a Intel-PC with Windows 10, using Visual Studio. sizeof (int) == sizeof (long int) (32 bits). This is independent whether I compile x86 code (32 bits) or x64 code (64 bits). The same is true for gcc (on cygwin in my case) as well as on any Intel-PC with Linux (AFAIK). For a granted larger type than int you have to choose long long int.

I did the sample session in cygwin on Windows 10 (64 bit):

$ g++ -std=c++11 -o karatsuba karatsuba.cc 

$ ./karatsuba
0 * 0 = 0 OK.
0 * 3 = 0 OK.
0 * 6 = 0 OK.

etc. etc.

999 * 993 = 992007 OK.
999 * 996 = 995004 OK.
999 * 999 = 998001 OK.
0 error(s).

$