为什么我在这个 Karatsuba 乘法中遇到逻辑错误？

Question

我已经阅读了许多博客和代码示例，但我正在尝试通过一种目前在逻辑上行不通的方式来实现 Karatsuba 乘法。只有个位数乘法有效，但任何长于 1 的数字都会显示完全错误的答案。它应该能够接受大量的输入，但我不允许使用 long int 存储类型。此外，它意味着能够将不同基数 (1-10) 的数字相乘，但我不确定如何做到这一点，所以最初我只是尝试以 10 为基数。到目前为止，这是我的代码：

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <sstream> 
int compareSize(string integer1, string integer2)
{
    int length = 0;
    if (integer1.length() > integer2.length())
    {
        //allocating int 1's length as final length if bigger than int 2
        length = integer1.length();
    }
    else if (integer2.length() > integer1.length())
    {
        //allocating int 2's length as final length if bigger than int 1
        length = integer2.length();
    }
    else
    {
        length = integer1.length();
    }

    return length;
}

int multiplication( string I1, string I2, int B){
    
    int length = compareSize(I1, I2);

    //converting the strings into integers
    stringstream numberOne(I1);
    int digitOne = 0;
    numberOne >> digitOne;

    stringstream numberTwo(I2);
    int digitTwo = 0;
    numberTwo >> digitTwo;

    //checking if numbers are single digits
    if ( (10 > digitOne) || (10 > digitTwo) ) {
        //cout<<(digitOne * digitTwo)<<endl;
        return (digitOne * digitTwo);
    }

    int size = ( length % 2) + (length / 2);

    int power = pow(10, size);

    int a = digitOne / power;   
    int c = digitTwo / power;   
    int b = digitOne - (a * power);  
    int d = digitTwo - (c * power);  

    int p2 = b * d;   
    int p0 = a * c;   
    int p1 = (b + a) * (d + c);
    //int final = p1 - p2 - p0;
    int sum = ((a*d) + (b*c)) ;

    int p = (p0*(pow(10,length))) + (sum * (pow(10,length)) + p2);
    //int p = ( p2 * (pow(10,size*2)) + ( p1 - (p2+p0)) * pow(10,size) + p0 ) * 100;
    // int p = (p2 * (long long)(pow(10, 2 * size))) + p0 + ((p1 - p0 - p2) * power);
    return p; 
}

int main(){

    string int1, int2;
    int base;
    cout<<"Enter I1, I2 and B: ";
        cin>> int1 >> int2 >> base;
    
    cout<<" "<<multiplication(int1, int2, base)<<endl;

    return 0;
    
}

Answer 1

主要问题是

int p = (p0*(pow(10,length))) + (sum * (pow(10,length)) + p2);

应该是

int p = (p0*(pow(10,length))) + (sum * (pow(10,length - 1)) + p2);

您不应将 std::pow 用于整数 GCC C++ pow accuracy。我用我自己的版本替换了它：

#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>

int pow(int b, int e) {
    if (e == 0) return 1;
    if (e == 1) return b;
    if (e % 2 == 0) return pow(b * b, e / 2);
    return b * pow(b * b, e / 2);
}

int multiplication(std::string I1, std::string I2) {
    
    int length = std::max(I1.length(), I2.length());
    int digitOne = std::stoi(I1);
    int digitTwo = std::stoi(I2);
    
    if ( (10 > digitOne) || (10 > digitTwo) ) {
        return (digitOne * digitTwo);
    }

    int size = ( length % 2) + (length / 2);

    int power = pow(10, size);

    int a = digitOne / power;   
    int c = digitTwo / power;   
    int b = digitOne - (a * power);  
    int d = digitTwo - (c * power);  

    int p2 = b * d;   
    int p0 = a * c;   
    int sum = ((a*d) + (b*c)) ;

    int p = (p0*(pow(10,length))) + (sum * (pow(10,length - 1)) + p2);
    return p; 
}

int main(){

    std::string int1, int2;
    std::cout<<"Enter I1 and I2: ";
    std::cin>> int1 >> int2;
    
    std::cout<<" "<<multiplication(int1, int2)<<'\n';

    return 0;
    
}

为什么我在这个 Karatsuba 乘法中遇到逻辑错误？

Why am I getting a logic error in this Karatsuba Multiplication?

c++

algorithm

recursion

multiplication