Patch for java.math.BigInteger class that increases multiply performance by using Karatsuba algorithm

BigInteger.java

...
  public BigInteger multiply(BigInteger val) {
      if (val.signum == 0 || signum == 0)
          return ZERO;

      int n = Math.max(bitLength(), val.bitLength());
      if (n > 1000)
          return multiplyKaratsuba(val, n);

      int[] result = multiplyToLen(mag, mag.length,
                                   val.mag, val.mag.length, null);
      result = trustedStripLeadingZeroInts(result);
      return new BigInteger(result, signum == val.signum ? 1 : -1);
  }
...
  private BigInteger multiplyKaratsuba(BigInteger val, int maxBitLength) {
      int n = (maxBitLength / 2) + (maxBitLength % 2);

      // x = a + 2^n * b,   y = c + 2^n * d
      BigInteger b = shiftRight(n);
      BigInteger a = subtract(b.shiftLeft(n));
      BigInteger d = val.shiftRight(n);
      BigInteger c = val.subtract(d.shiftLeft(n));

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

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