GCD大整数.rar_K8YT_gcd_hurtuwe_stein

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); } }