使用 Karatsuba 乘法（递归高斯 "trick"）将两个大数相乘时无法得到正确答案

Question

我一直在尝试使用字符串来实现整数乘法问题。较小数字的乘积总是正确的，但对于较大数字，结果是错误的。
谁能告诉我是哪部分代码导致了问题？

一个：3141592653589793238462643383279502884197169399375105820974944592

b: 2718281828459045235360287471352662497757247093699959574966967627

答案：8539734222646569768352026223696548756537378365658178539814559622482948999279606844390394705148206869490910283679004[84736215]

正确答案：853973422267356706546355086954657449503488853576511496187960112706774304489320484861787507221624907301333748951871211=854[720=854]


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

Answer 1

您在 getEqualLength 中有一个简单的错误。它应该 return a.length() 或 b.length()。这是更正后的代码：

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

}

使用 Karatsuba 乘法（递归高斯 "trick"）将两个大数相乘时无法得到正确答案

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

c++

string

algorithm

multiplication

karatsuba