1

我正在尝试在这里进行 Karatsuba 乘法。下面的代码适用于两位数的数字（例如 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的结果后，接下来的计算是错误的。

在此处输入图像描述

4

1 回答 1

2

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

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

于 2021-04-17T08:23:44.447 回答