2

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.

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • What do you really want? return 1221 could solve youre problem now ;-). Please give more information.. – Finduilas May 11 '17 at 06:41
  • Welcome to StackOverflow. Please take the [tour]. If you are looking for help with debugging code see https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ Apart from "use gdb" the text has many other good hints. Maybe you can exercise using a debugger first, based on explicitly simple programs you understand anyway. That is another useful skill next to algorhitmic thinking. – Yunnosch May 11 '17 at 06:41
  • Use the debugger by putting breakpoints all over your program. Normally you can see the value of your variables at particular moments and then guess where it goes wild. – Badda May 11 '17 at 06:48
  • You're right I see it now (after I had my cup of tea) still look here for comparison [Fast bignum square computation](http://stackoverflow.com/q/18465326/2521214) you can use both mine and yours ... step in both with the same input and compare subresults where it goes wrong... – Spektre May 11 '17 at 08:30
  • Btw why your karatsuba returns `long` when your inputs are `string`s? if you return string then you will not be bounded by long bit-width. – Spektre May 12 '17 at 06:17
  • I know, I'll probably fix that too. For now I'm just focusing on making this work. – Shikhar Jaiswal May 12 '17 at 08:29
  • Don't worry, it is good question. – peterh May 14 '17 at 18:17
  • The length of the *less* significant parts needs to be the one used in scaling intermediate results. – greybeard Mar 21 '19 at 21:06

0 Answers0