java - 使用 BigInteger 实现 karatsuba 算法时出错

Question

我正在尝试使用 Java 起诉 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);语句.

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

Answer 1

这里是 Karatsuba algorithm implementation来自普林斯顿大学“Java 编程入门”类(class):

  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));
  }

我觉得你可以大胆使用。