Karatsuba Multiplication

import java.math.BigInteger;

public class Karatsuba {

    public static void main(String[] args) {
        BigInteger a = rand(100000), b = rand(100000);
        long t = System.currentTimeMillis();
        a.multiply(b);
        System.out.println("Naive Multiplication (ms)"+(System.currentTimeMillis() - t));
        t = System.currentTimeMillis();
        karatsuba(a, b);
        System.out.println("Karatsuba Multiplication (ms)"+(System.currentTimeMillis() - t));
    }

    static BigInteger karatsuba(BigInteger x, BigInteger y){
        BigInteger m,a,b,c,xl,xh,yl,yh;
        m = sqrt(x); m = nextPowerOf2(m);
        xl = x.mod(m); xh = x.divide(m);
        yl = y.mod(m); yh = y.divide(m);
        c = xl.multiply(yl);
        b = xl.add(xh).multiply(yl.add(yh));
        a = xh.multiply(yh);
        return a.multiply(m.pow(2)).add(b.subtract(a).subtract(c).multiply(m)).add(c);
    }

    static BigInteger sqrt(BigInteger x) {
        BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
        BigInteger div2 = div;
        for(;;) {
            BigInteger y = div.add(x.divide(div)).shiftRight(1);
            if (y.equals(div) || y.equals(div2))
                return y;
            div2 = div;
            div = y;
        }
    }

    static BigInteger rand(int n){
        String nb = "";
        while( n>0 ){
            nb += (int) (Math.random()*10);
            n--;
        }
        return new BigInteger(nb);
    }

    static BigInteger nextPowerOf2( BigInteger n)
    {
        return BigInteger.valueOf(2).pow(n.bitLength());
    }
}