Java中的Karatsuba乘法

Question

我想在这里做卡拉特赛乘法。下面的代码适用于两位数的数字(例如78 * 34)，但对于数字大于2的数字(例如5678 * 1234)，则给出错误的结果。我已经附加了调试日志。在某一点之后，计算是错误的。有人能看看我对算法的理解是否不正确吗？

static BigInteger karatsuba(BigInteger no1, BigInteger no2){
    BigInteger result = null;
    
    //Both numbers less than 10
    if(no1.compareTo(new BigInteger("9")) != 1 && no2.compareTo(new BigInteger("9")) != 1 ){
        return no1.multiply(no2);
    }
    
    String str1 = no1.toString();
    String str2 = no2.toString();
            
    if(str1.length() ==1) {
        str1 = "0" + str1;
    }
    if(str2.length() ==1) {
        str2 = "0" + str2;
    }
    
    int m = str1.length()/2;
    String a = str1.substring(0,m);
    String b = str1.substring(m,str1.length()); 
    
    m = str2.length()/2;
    String c = str2.substring(0,m);
    String d = str2.substring(m,str2.length());
    
    BigInteger step1 = karatsuba(new BigInteger(a),new BigInteger(c)); 
    BigInteger step2 = karatsuba(new BigInteger(b),new BigInteger(d)); 
    BigInteger step3 = karatsuba(new BigInteger(a).add(new BigInteger(b)),new BigInteger(d).add(new BigInteger(c)));
    BigInteger step4 = step3.subtract(step2).subtract(step1);
    
    int n = str1.length() > str2.length() ? str1.length() : str2.length();
    
    double db = Math.pow(10,n);
    double dbby2 = Math.pow(10,(n/2));
    
    step1 = step1.multiply(BigDecimal.valueOf(db).toBigInteger());
    step4 = step4.multiply(BigDecimal.valueOf(dbby2).toBigInteger());
    
    result = step1.add(step4).add(step2);
    return result;
}

调试日志：

在得到2652的结果后，下一个计算是错误的。

​

​

Answer 1

一个明显的错误是，乘法器被错误地填充了零。

if ((str1.length() & 1) == 1) {
    str1 = "0" + str1;
}
while (str2.length() < str1.length()) {
    str2 = "0" + str2;
}

这是第二个错误：

由于错误的pow函数在指数中舍入误差

step1 = step1.multiply(BigInteger.valueOf(10L).pow(n));
step4 = step4.multiply(BigInteger.valueOf(10L).pow(n/2));

5678 * 1234 = 7006652

84232332233 * 1532664392 = 129099896268632947336

在填充零之前：str1的长度必须始终大于或等于str2的长度