Ошибка при реализации алгоритма Карацубы с BigInteger

Question

Я пытаюсь реализовать алгоритм karatsuba с помощью Java, предъявляя иск BigInteger, я выполнил все шаги, но не получаю правильный результат, что сводит меня с ума.

Вот мой код:

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!!!. и я отладил, сюрприз был в том, что когда поток выполнения прибывает в оператор return, программа не останавливается, а переходит к BigInteger t2 = karatsuba(a0, b0, base);заявление.

Поэтому я не знаю, что я делаю не так. Любая помощь будет принята с благодарностью.

Answer 1

Вот реализация алгоритма Карацубы из Принстонского университета, курс "Введение в программирование на Java":

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

Я думаю, что вы можете смело использовать это.