can't get the right answer when multiplying two large numbers using Karatsuba multiplication(recursive Gauss "trick")

Question

I have been trying to implement integer-multiplication problems using strings. The product of smaller numbers is always right but for larger numbers the results are wrong.
Can anyone tell me which part of the code is causing the problem?

a: 3141592653589793238462643383279502884197169399375105820974944592

b: 2718281828459045235360287471352662497757247093699959574966967627

answer: 8539734222646569768352026223696548756537378365658178539814559622482948999279606844390394705148206869490910283679048366582723184

correct answer: 8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184


int getEquallength(string &a,string &b)
{
    int n1=a.length();
    int n2=b.length();
    if(n1>n2)
    {
        for(int i=0;i<n1-n2;i++)
        {
            b='0'+b;
        }
    }
    else if(n2>n1)
    {
        for(int i=0;i<n2-n1;i++)
        {
            a='0'+a;
        }
    }
    return n1;
}
string addstrings(string a,string b)
{
    int n=getEquallength(a,b);
    n=a.length();
    string result="";
    int carry=0;
    for(int i=n-1;i>=0;i--)
    {
        int f=a[i]-'0';
        int s=b[i]-'0';

        int sum=f+s+carry;
        carry=sum/10;
        sum=sum%10+'0';
        result=char(sum)+result;
    }
    if(carry) result=char(carry+'0')+result;
    return result;
}
string substract_str(string a,string b)
{
    int n=getEquallength(a,b);
    int carry=0;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    
    string result;
    for(int i=0;i<a.length();i++)
    {
        int f=a[i]-'0';
        int s=b[i]-'0';
        int sub=0;
        sub=f-s-carry;
        if(sub<0)
        {
            sub+=10;
            carry=1;
        }
        else
            carry=0;  
        result=char(sub+'0')+result;

    }

    return result;
}
string karatsuba(string a,string b)
{
    int n=getEquallength(a,b);
    if(n==0) return "0";
    if(n==1)
    {
        return to_string(atoi(a.c_str())*atoi(b.c_str()));
    }
    int fh=n/2;
    int sh=n-n/2;

    string Xl=a.substr(0,fh);
    string Xr=a.substr(fh,sh);
    string Yl=b.substr(0,fh);
    string Yr=b.substr(fh,sh);

    string P1=karatsuba(Xl,Yl);
    string P2=karatsuba(Xr,Yr);

    string res=addstrings(P1,P2);

    string P3=karatsuba(addstrings(Xl,Xr),addstrings(Yl,Yr));// (Xl+Xr)*(Yl+Yr)

    P3=substract_str(P3,res);//P3=Xl*Yr+Xr.Yl

    for(int i=0;i<2*sh;i++)
    {
        P1.push_back('0');
    }
    for(int i=0;i<sh;i++)
    {
        P3.push_back('0');
    }




    P1= addstrings(P1,P2);

    string result=addstrings(P1,P3);
    return result;
}

Use a debugger to step through the code, that way you can easily tell where it goes wrong. Also, in case you haven't, write unit tests to ensure proper operation. As a new user here, please also take the [tour] and read [ask]. For a proper [mcve], it would be necessary to remove the manual input and hard-code example numbers that fail, though that's more of a nitpick in this specific case. — Ulrich Eckhardt, Feb 21 '22 at 18:17
https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h, BTW. Also, I highly doubt your code compiles without warnings. Consider fixing every single one of them. — Ulrich Eckhardt, Feb 21 '22 at 18:19
I'd suggest testing `addstrings` and `substract_str` on their own and making sure they both work correctly then you can test `karutsuba`, that should help you narrow down where the bug(s) lie — Alan Birtles, Feb 21 '22 at 18:49
you never need to include `bits/xx`. also dont do `using namespace std`. read https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice — pm100, Feb 21 '22 at 19:27

score 1 · Accepted Answer · answered Feb 21 '22 at 19:24

You have a simple error in getEqualLength. It should return a.length() or b.length(). Here's the corrected code:

//#include <bits/stdc++.h>
#include <string>
#include <iostream>

using namespace std;
int getEquallength(string& a, string& b)
{
    int n1 = a.length();
    int n2 = b.length();
    if (n1 > n2)
    {
        for (int i = 0; i < n1 - n2; i++)
        {
            b = '0' + b;
        }
    }
    else if (n2 > n1)
    {
        for (int i = 0; i < n2 - n1; i++)
        {
            a = '0' + a;
        }
    }
    return a.length();
}
string addstrings(string a, string b)
{
    int n = getEquallength(a, b);
    n = a.length();
    string result = "";
    int carry = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        int f = a[i] - '0';
        int s = b[i] - '0';

        int sum = f + s + carry;
        carry = sum / 10;
        sum = sum % 10 + '0';
        result = char(sum) + result;
    }
    if (carry) result = char(carry + '0') + result;
    return result;
}
string substract_str(string a, string b)
{
    int n = getEquallength(a, b);
    int carry = 0;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string result;
    for (int i = 0; i < a.length(); i++)
    {
        int f = a[i] - '0';
        int s = b[i] - '0';
        int sub = 0;
        sub = f - s - carry;
        if (sub < 0)
        {
            sub += 10;
            carry = 1;
        }
        else
            carry = 0;
        result = char(sub + '0') + result;

    }

    return result;
}
string karutsuba(string a, string b)
{
    int n = getEquallength(a, b);
    if (n == 0) return "0";
    if (n == 1)
    {
        return to_string(atoi(a.c_str()) * atoi(b.c_str()));
    }
    int fh = n / 2;
    int sh = n - n / 2;

    string Xl = a.substr(0, fh);
    string Xr = a.substr(fh, sh);
    string Yl = b.substr(0, fh);
    string Yr = b.substr(fh, sh);

    string P1 = karutsuba(Xl, Yl);
    string P2 = karutsuba(Xr, Yr);

    string res = addstrings(P1, P2);

    string P3 = karutsuba(addstrings(Xl, Xr), addstrings(Yl, Yr));// (Xl+Xr)*(Yl+Yr)

    P3 = substract_str(P3, res);//P3=Xl*Yr+Xr.Yl

    for (int i = 0; i < 2 * sh; i++)
    {
        P1.push_back('0');
    }
    for (int i = 0; i < sh; i++)
    {
        P3.push_back('0');
    }




    P1 = addstrings(P1, P2);

    string result = addstrings(P1, P3);
    return result;
}
int main()
{
    string a, b;
    cout << "a:" << '\n';
    cin >> a;
    cout << "b:" << '\n';
    cin >> b;
    int n = getEquallength(a, b);
    cout << karutsuba(a, b);

}

can't get the right answer when multiplying two large numbers using Karatsuba multiplication(recursive Gauss "trick")

1 Answers1