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.

not a JAVA coder so I may be wrong but: 1. `Math.pow(base, mitad)` is suspicious as the result is `float` which will most likely not fit the result in. 2. Karatsuba is recursive so all recursion layers must be called in before final return will really return ... As I do not use big integer I am not sure if `a.divide,a.remainder` is really doing what you want. If it is really division and modulus then that is wrong as you need to divide internal representation of bigint not the number itself otherwise you would use bigint `/,%` for bigint `*` which is insanity. — Spektre, Feb 04 '17 at 04:48
This is probably not your problem (since 1252 and 532 are well within the range of non-Big integers), but `Math.pow` is very unlikely to work right for actual big integers. This is also probably not your problem (since you are testing with `base` set to 10), but `a.toString().length()` is unlikely to compute the right size unless `base` is 10. — Daniel Wagner, Feb 04 '17 at 04:50
btw here [Fast bignum square computation](http://stackoverflow.com/q/18465326/2521214) you can find at the end my arbnum Karatsuba implementation in C++ (arbnum is arbitrary mantissa float so you can ignore the exponent stuff for bigints) — Spektre, Feb 04 '17 at 04:51

score 2 · Accepted Answer · answered Mar 11 '17 at 09:46

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.

Error Implementing the karatsuba algorithm with BigInteger

1 Answers1