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 '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;
}

CodePudding user response：

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

}