Karatsuba

package complejidad;

import java.math.BigInteger ;
import java.util.Random;



public class Karatsuba {


    public static BigInteger multiplicar (BigInteger x, BigInteger y){

        int m = Math.max(x.bitLength(), y.bitLength())/2 ;

        if(m<=10){
            return x.multiply(y);
        }
        BigInteger x1 = x.shiftRight(m);// googlear shift left y right ;
        BigInteger y1= y.shiftRight(m);


        BigInteger x2 = x.subtract( x1.shiftLeft(m));
        BigInteger y2 = y.subtract( y1.shiftLeft(m));


        BigInteger A = multiplicar(x1,y1);
        BigInteger B = multiplicar(x2,y2);
        BigInteger C = multiplicar(x1.add(x2),y1.add(y2));

        BigInteger K = C.subtract(A.add(B));


        return A.shiftLeft(2*m).add(K.shiftLeft(m)).add(B);

    }

    public static void main(String[] args) {
//      Random random = new Random(0);
//      int digitos = 1800;
//      BigInteger x= new BigInteger(digitos,random);
//      BigInteger y= new BigInteger(digitos,random);
//
//      System.out.println("x= "+x);
//      System.out.println("y= "+y);
//      BigInteger suma = x.add(y);
//
//
//      System.out.println(suma);
//
//      long inicio = System.currentTimeMillis();
//      BigInteger zk = multiplicar(x,y);
//      BigInteger zp = x.multiply(y);
//
//      System.out.println("asd="+zk);
//      System.out.println("asd="+zp);
//
//
//      long fin = System.currentTimeMillis();
//      double tiempo = (double) (fin-inicio)/1000;
//      System.out.println(tiempo + " seg");
//
//
        Random random =new Random (0);
        BigInteger x= new BigInteger(1800,random);
        BigInteger y= new BigInteger(1800,random);

    int cantidad =100000;
    long inicio =System.currentTimeMillis();
    long fin = System.currentTimeMillis();
    double tiempo = (fin-inicio) / (1000.0* cantidad);
    System.out.println( tiempo + "sg");

    }

}