使用BigInteger实现karatsuba算法错误

我正在尝试使用Java来起诉BigInteger的karatsuba算法，我遵循了所有步骤，但是我没有得到正确的结果，是什么让我发疯。使用BigInteger实现karatsuba算法错误

这里是我的代码：

public BigInteger karatsuba(BigInteger a, BigInteger b, int base) { 
    if (a.compareTo(BigInteger.TEN) == -1 || b.compareTo(BigInteger.TEN) == -1) { 
     return a.multiply(b); 
    } 

    /* calculates the size of the numbers */ 
    int tam = a.toString().length(); 
    int mitad = tam/2; 


    BigInteger a1 = (a.divide(BigInteger.valueOf((long) Math.pow(base, mitad)))); 
    BigInteger a0 = (a.remainder(BigInteger.valueOf((long) Math.pow(base, mitad)))); 

    BigInteger b1 = (b.divide(BigInteger.valueOf((long) Math.pow(base, mitad)))); 
    BigInteger b0 = (b.remainder(BigInteger.valueOf((long) Math.pow(base, mitad)))); 

    /* 3 calls made to numbers approximately half the size */ 
    BigInteger t1 = karatsuba(a1, b1, base); 
    BigInteger t2 = karatsuba(a0, b0, base); 
    BigInteger t3 = karatsuba(a1.add(a0), b1.add(b0), base); 

    BigInteger aux1 = (t1.multiply(BigInteger.valueOf((long)Math.pow(base, tam)))); 
    BigInteger aux2 = t1.subtract(t2); 
    BigInteger aux4 = aux2.subtract(t3); 
    BigInteger aux3 = aux4.multiply(BigInteger.valueOf((long) Math.pow(base,mitad)).add(t2)); 

    return aux1.add(aux3); 

}

我测试的代码如下条目：karatsuba(new BigInteger("1252",new BigInteger("532") , 10)而正确的结果是666064，我得到2212864 !!!并且我调试了，令人惊讶的是，当执行流程到达返回语句时，程序不会停止，但会进入BigInteger t2 = karatsuba(a0, b0, base);声明。

所以我不知道我在做什么错。任何帮助将不胜感激。

来源

2017-02-04 shadow

不是JAVA编码器，所以我可能是错的，但：1. Math.pow（base，mitad）是可疑的，因为结果是'float'，这很可能不适合结果。2. Karatsuba是递归所以所有的递归层必须在最终返回之前调用才会真正返回...因为我不使用大整数，所以我不确定'a.divide，a.remainder是否真的在做你想要的。如果它真的是分割和模数，那么这是错误的，因为你需要划分bigint的内部表示而不是数字本身，否则你会使用bigint'/，％'作为bigint'*'，这是疯狂。 – Spektre

这可能不是你的问题（因为1252和532完全在非Big整数范围内），但'Math.pow'不太可能适用于实际的大整数。这也可能不是你的问题（因为你正在测试'base'设置为10），但是'a.toString（）.length（）'不可能计算出正确的大小，除非'base'是10. –

btw [快速bignum平方计算]（http://stackoverflow.com/q/18465326/2521214）你可以在最后找到我的arbnum Karatsuba在C++中的实现（arbnum是任意的mantissa float，所以你可以忽略bigint的指数） – Spektre

这里是当然普林斯顿大学“使用Java程序设计入门” Karatsuba algorithm implementation：

public static BigInteger karatsuba(BigInteger x, BigInteger y) { 

    // cutoff to brute force 
    int n = Math.max(x.bitLength(), y.bitLength()); 
    if (n <= 10) return x.multiply(y); 

    // number of bits divided by 2, rounded up 
    n = (n/2) + (n % 2); 

    final BigInteger b = x.shiftRight(n); 
    final BigInteger a = x.subtract(b.shiftLeft(n)); 
    final BigInteger d = y.shiftRight(n); 
    final BigInteger c = y.subtract(d.shiftLeft(n)); 

    // compute sub-expressions 
    final BigInteger ac = karatsuba(a, c); 
    final BigInteger bd = karatsuba(b, d); 
    final BigInteger abcd = karatsuba(a.add(b), c.add(d)); 

    return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(n)).add(bd.shiftLeft(2 * n)); 
    }

我认为你可以大胆地使用它。

来源

2017-03-11 09:46:36 Nolequen

使用BigInteger实现karatsuba算法错误

回答

相关问题