C++实现字符串存储的任意进制Karatsuba乘法输出错误排查求助

问题背景 #

实现基于字符串存储的任意进制大整数运算，支持指定进制的加法与Karatsuba乘法功能。输入格式为int1 int2 base，其中int1、int2为待运算的大整数，base为数字进制；输出格式为add mult，add为两个整数按竖式加法得到的和，mult为Karatsuba乘法得到的积。

输入输出样例 #

输入样例 #

1231000323012031333233201313312322110321130022201222133322033312000313333113222010300133031211311 10203302031023112301210030203002033323 4

预期输出 #

1231000323012031333233201313312322110321130022201222133322110121303011022232123220331002033311300 
490306232475117580392628428529303475424922697851904379576867313243824589283681700912220831308362948505562812188832489817917769878090

错误代码 #

字符串加法函数 #

// The main function that adds two bit sequences and returns the addition
string add_strings(string a, string b){
    string result ;  // To store the sum bits
    // make the lengths same before adding
    int length = max(a.length(), b.length()) ;
    while (a.length() < length) a.insert(0, "0") ;
    while (b.length() < length) b.insert(0, "0") ;
    // Initialize carry
    int carry = 0 ;
    // Add all bits one by one
    for (int i = length - 1 ; i > -1 ; i--)
    {
        int aBit = a[i] - '0' ;
        int bBit = b[i] - '0' ;
        // Boolean expression for sum of 3 bits
        int sum = aBit + bBit + carry ;
        // Update carry
        carry = sum / base ;
        // Update sum for string insertion
        sum = sum % base ;
        // Update sum result
        result.insert(0, to_string(sum)) ;
    }
    // if overflow, then add the carry
    if (carry)  result.insert(0, to_string(carry)) ;
    return result.erase(0, min(result.find_first_not_of('0'), result.size() - 1)) ;
}

字符串减法函数 #

// Function for find difference of larger numbers
string sub_strings(string a, string b, int base)
{
    // Ensure the first string is bigger than the second
    // Therefore no negative cases, no carry needed
    int comp = a.compare(b) ;
    if (comp < 0) swap(a, b) ;
    // Make the lengths same before subtracting
    int length = max(a.length(), b.length()) ;
    while (a.length() < length) a.insert(0, "0") ;
    while (b.length() < length) b.insert(0, "0") ;
    // Initialise result string
    string result = "";
    int diff, carry ;
    // Subtraction
    for (int i = length - 1; i > -1; i--) {
        // Find difference of each digit
        int aBit = a[i] - '0' ;
        int bBit = b[i] - '0' ;
        diff = (aBit - bBit) / base ;
        result.insert(0, to_string(diff)) ;
     }
    // reverse resultant string
    reverse(result.begin(), result.end());
    return result.erase(0, min(result.find_first_not_of('0'), result.size() - 1)) ; 
}

左移（乘进制幂）函数 #

void leftShift(string &ab, int k){
reverse(ab.begin(), ab.begin() + 1) ;
reverse(ab.begin() + 1, ab.end()) ;
reverse(ab.begin(), ab.end()) ; 
}

Karatsuba主实现 #

string Karatsuba(string a, string b, int base){
// Base cases
int length = max(a.length(), b.length());
if (length == 0) return 0 ;
if (length == 1) return to_string((a[0] - '0')*(b[0] - '0')) ;
// Add leading zeros to ensure numbers are the same size
while (a.length() < length) a.insert(0, "0") ;
while (b.length() < length) b.insert(0, "0") ;
// Split a into (a0, a1) and b into (b0, b1)
int k = length / 2 ;
int upper = length - k ;
// convert the above vectors to strings for multiplication
// need separate for loops to prevent out of range errors
string a0 = a.substr(k) ;
string a1 = a.substr(0, upper) ;
string b0 = b.substr(k) ;
string b1 = b.substr(0, upper) ;
// Compute the three products
// p0 = a0b0, p1 = (a1+a0)*(b1+b0), p2 = a1b1
string p0 = Karatsuba(a0, b0, base) ;
string p1 = Karatsuba(add_strings(a1, a0, base), add_strings(b1, b0, base), base) ;
string p2 = Karatsuba(a1, b1, base) ;
//ab = p2 * (pow(base, 2*k)) + (p1 - (p2 + p0)) * pow(base, k) + p0
// term1 = p2 * (pow(base, 2*k))
// term2 = (p1 - (p2 + p0)) * pow(base, k)
string term2 = sub_strings(add_strings(p2, p0, base), p1, base) ;
leftShift(p2, k) ;
leftShift(p2, k) ;
leftShift(term2, k) ;
// term3 = p0
// Add leading zeros
for (int i = 0; i < upper; i++) p0.append("0") ;
for (int i = 0; i < upper; i++) term2.append("0") ;
string result = add_strings(add_strings(p2, p0, base), term2, base) ;
return result.erase(0, min(result.find_first_not_of('0'), result.size() - 1));
}

错误点汇总 #

• 加法函数参数缺失：add_strings没有接收base参数，函数内部用到的base是未定义变量，需修改函数声明为string add_strings(string a, string b, int base)。
• 减法函数逻辑完全错误：未处理借位逻辑，diff = (aBit - bBit) / base计算规则错误，且末尾多余执行了一次reverse操作，导致结果顺序完全颠倒。
• 左移函数功能完全错误：现有三次反转的逻辑和乘进制幂（末尾加k个0）没有任何关联，也没有用到传入的移位次数参数k，正确实现直接在字符串末尾追加k个'0'即可。
• Karatsuba公式符号错误：公式要求term2 = p1 - (p2 + p0)，现有代码调用sub_strings(add_strings(p2,p0,base), p1, base)得到的是(p2+p0) - p1，数值完全相反。
• 重复移位错误：已经对p2、term2执行了左移操作，后续又给p0、term2追加了upper个0，相当于重复移位，导致结果量级完全错误。
• 边界返回值错误：长度为0的边界case直接返回整数0，没有返回字符串"0"，类型转换会引发未定义行为。

内容的提问来源于stack exchange，提问作者melarnmurphy