package gcd;
import java.math.BigInteger;
import java.util.*;
public class stein_gcd{
public static BigInteger gcdBinary(BigInteger u,BigInteger v){
u=(u.compareTo(BigInteger.ZERO)<0)?u.negate():u;
v=(v.compareTo(BigInteger.ZERO)<0)?v.negate():v;
BigInteger b_2 = new BigInteger("2");
//System.out.println("u="+u+",v="+v+" ?="+b_2);
while(true){
if(u.compareTo(BigInteger.ZERO)==0 && v.compareTo(BigInteger.ZERO)!=0){
return v;
}
else if(u.compareTo(BigInteger.ZERO)!=0 && v.compareTo(BigInteger.ZERO)==0){
return u;
}
else if(u.remainder(b_2)==BigInteger.ZERO && v.remainder(b_2)==BigInteger.ZERO){
return b_2.multiply(gcdBinary(u.divide(b_2),v.divide(b_2)));
}
else if(u.remainder(b_2)!=BigInteger.ZERO && v.remainder(b_2)==BigInteger.ZERO){
return (gcdBinary(u,v.divide(b_2)));
}
else if(u.remainder(b_2)==BigInteger.ZERO && v.remainder(b_2)!=BigInteger.ZERO){
return (gcdBinary(u.divide(b_2),v));
}
else if(u.remainder(b_2)!=BigInteger.ZERO && v.remainder(b_2)!=BigInteger.ZERO
&& u.compareTo(v)>=0){
return gcdBinary((u.subtract(v)).divide(b_2),v);
}
else if(u.remainder(b_2)!=BigInteger.ZERO && v.remainder(b_2)!=BigInteger.ZERO
&& u.compareTo(v)<=0){
return gcdBinary(u,(v.subtract(u)).divide(b_2));
}
}
}
public static void print(BigInteger m,BigInteger n,BigInteger gcd){
System.out.format("gcd of \n%d \nand \n%d\n is: %d\n",m,n,gcd);
}
public static void main(String[] args) {
/**Random random = new Random();
int ran = 0;
String str1="",str2="";
for(int i=0;i<10;i++){
ran = random.nextInt(10);
str1 += ran+"";
ran = random.nextInt(10);
str2 += ran+"";
}
BigInteger m = new BigInteger(str1);
BigInteger n = new BigInteger(str2);*/
BigInteger m = new BigInteger("1234567890987654321234567890987654321234");
BigInteger n = new BigInteger("5678909876543212345678909876543212345678");
long t1=System.currentTimeMillis();
//print(m,n,gcdBinary(m,n));
System.out.println(gcdBinary(m,n));
BigInteger g = gcdBinary(m,n);
long t2=System.currentTimeMillis();
System.out.println("\ntime used��");
System.out.println(((double)(t2-t1))/1000);
}
}
