学以致用——最大公約数計算の3種類の異なるアルゴリズムの比較(蛮力、ユークリッドアルゴリズム及び転がり相除算法)

データ構造を学んだ後、以前書いた簡単なプログラムの多くは原始的なアルゴリズムを使っているような気がします.
今日、浙大中国大学MOOCの「プログラム設計入門-C言語」課程で、最大公約数解の新しい方法--転々と相殺法を見た.ちょうど前の蛮力アルゴリズムやユークリッドアルゴリズムと比較することができます.
参考記事:
Javaソース-最大公約数計算の一般的なアルゴリズムとユークリッドアルゴリズムの比較を学ぶ(Greatest Common Divisor)
https://blog.csdn.net/hpdlzu80100/article/details/85228095
 
実行結果:
1番目の整数を入力してください(入力-1終了):3333333333 2番目の整数を入力してください(入力-1終了):666666666メソッド1:33333333および66666666666の最大公約数は:3333333333、共用時3765850951.000ナノ秒メソッド2:3333333333および66666666666の最大公約数は:33333333333333、33333、共用時24474.00000ナノ秒法2の使用時は方法1の0.00064930%方法3:33333333および666666666の最大公約数:33333333,333,共用時59210000000ナノ秒法3の使用時は方法1の0.0001572287%である  1番目の整数(入力-1終了):4444444444を入力してください2番目の整数(入力-1終了):88888888メソッド1:4444444444および8888888888の最大公約数:444444444444、共通時4976811991200000ナノ秒メソッド2:444444444444および8888888888の最大公約数:44444444444444、44444444444444、共用時1184.000000ナノ秒方法2の使用時が方法1の0.000023790%方法3:4444444444と8888888888の最大公約数:4444444444、共用時789.00000ナノ秒方法3の使用時が方法1の0.000015854%である
結論:
蛮力アルゴリズム、ユークリッドアルゴリズム、転がり相除去法の3つのアルゴリズムの中で、転がり相除去法の実行効率が最も高い!
 
コードは次のとおりです.

package exercises.ch6Methods;

import java.util.*;

//JHTP Exercise 6.27 (Greatest Common Divisor)
//by [email protected]
/**
 * 
 *6.27 (Greatest Common Divisor) The greatest common divisor (GCD) of two integers is the 
 *largest integer that evenly divides each of the two numbers. Write a method gcd that 
 *returns the greatest common divisor of two integers. [Hint: You might want to use Euclid’s algorithm. 
 *You can find information about it at en.wikipedia.org/wiki/Euclidean_algorithm.] Incorporate the method 
 *into an application that reads two values from the user and displays the result.
 *
 */

public class GreatedCommonDivisor {


	
	//       2008           ，https://blog.csdn.net/hpdlzu80100/article/details/2290499
	public static long gcd1(long n1, long n2) {
		
	long g = 0;
	
	for(long i=1;i<=Math.min(n1,n2);i++)
	{
	if (n1 % i == 0 && n2 % i == 0)
	   g = i;
	}

	return g;
}
	
	//   https://blog.csdn.net/jiaolipe/article/details/1476068，   Euclid’s algorithm（      ）
    private static long gcd2 (long num1, long num2){
        while (num1 != num2)
        {
           if (num1 > num2)
              num1 = num1 - num2;
           else
              num2 = num2 - num1;
        }

        return num1;
   }

    
	//     ，           MOOC《      ——C  》    
    private static long gcd3 (long num1, long num2){
    	
    	long temp = 0;
    	
    	//  num2<=num1，    
    	if(num2>num1) {
    		temp = num2;
    		num2 = num1;
    		num1 = temp;
    	}
    	
    	//     
        while (num2 != 0)
        {
           temp = num1 % num2;
           num1 = num2;
           num2 = temp;
        }

        return num1;
   }


	public static void main(String args[]) {
		long number1;
		long number2;
		long gcd1;
		long gcd2;
		long gcd3;
		
	    Scanner scan=new Scanner(System.in);
	    
	    do {
	    System.out.printf("        (  -1  )：");
	    number1 = scan.nextLong();
		if(number1 == -1)
		{System.out.print("     。");
		    break;
	    }
		
	    System.out.printf("        (  -1  )：");
	    number2 = scan.nextLong();
		if(number2 == -1)
		{System.out.print("     。");
		    break;
	    }
	    
		long beginTime=System.nanoTime();	
		gcd1 = gcd1(number1, number2);
		long endTime=System.nanoTime();
		double duration1=(double)(endTime-beginTime);
	    System.out.printf("  1：%d %d       ：%d，   %f  %n", number1, number2, gcd1, duration1);
	    
		beginTime=System.nanoTime();	
		gcd2 = gcd2(number1, number2);
		endTime=System.nanoTime();
		double duration2=(double)(endTime-beginTime);
	    System.out.printf("  2：%d %d       ：%d，   %f  %n", number1, number2, gcd2, duration2);
	    System.out.printf("  2      1 %.10f%%%n", duration2/duration1 * 100);
	    
		beginTime=System.nanoTime();	
		gcd3 = gcd3(number1, number2);
		endTime=System.nanoTime();
		double duration3=(double)(endTime-beginTime);
	    System.out.printf("  3：%d %d       ：%d，   %f  %n", number1, number2, gcd3, duration3);
	    System.out.printf("  3      1 %.10f%%%n", duration3/duration1 * 100);
	    
	    System.out.println();
	    } while (number1 != -1);
	    
	    System.out.println("     。");
	    scan.close();
	}
	}