Error Implementing the karatsuba algorithm with BigInteger

Question

I am trying to implement the karatsuba algorithm with Java suing BigInteger, I followed all the steps, but I am not getting the correct result, what is making me crazy.

Here is my code:

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

}

I tested the code with the following entry: karatsuba(new BigInteger("1252",new BigInteger("532") , 10) while the correct result is 666064 , I get 2212864 !!!. and I debugged, the surprise was that when the execution flow arrives to the return statement the program does not stop, but it goes to the BigInteger t2 = karatsuba(a0, b0, base);statement.

So I do not know what I am doing wrong. Any help would be very appreciated.

Answer 1

Here is Karatsuba algorithm implementation from Princeton University "Introduction to programming in Java" course:

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

I think you can boldly use it.