転がり相除法(ユークリッドアルゴリズムとも呼ばれる)は何の鬼ですか.

2つの正の整数の最大公約数を求めることを目的として、転々とした相殺法、別名ユークリッドアルゴリズム(Euclidean algorithm).
このアルゴリズムは、2つの正の整数aおよびb(a>b)に基づいており、それらの最大公約数は、aをbで割った余りcおよびbの間の最大公約数に等しい.例えば、10および25、25を10商2余り5で割った場合、10および25の最大公約数は、10および5の最大公約数に等しい.
更に相減損術は、中国古代の「九章算術」から出ており、最大公約数を求めるアルゴリズムでもある.
彼の原理はもっと簡単です:2つの正の整数aとb(a>b)で、それらの最大公約数はa-bの差cと小数bの最大公約数に等しいです.例えば、10と25、25から10を引く差は15で、10と25の最大公約数は10と15の最大公約数に等しいです.

package com.zheting.it.test04;

public class Test {

    public static void main(String[] args) {

    }

    //   
    public static int getGreatestCommonDivisor(int numberA, int numberB) {
        int smallNumber = numberA < numberB ? numberA : numberB;
        int bigNumber = numberA >= numberB ? numberA : numberB;
        if (bigNumber % smallNumber == 0) {
            return smallNumber;
        }
        int gereatestCommonDiveisor = 1;

        for (int i = 2; i < smallNumber / 2; i++) {
            if (numberA % i == 0 && numberB % i == 0) {
                gereatestCommonDiveisor = i;
            }
        }
        return gereatestCommonDiveisor;
    }

    //            a b（a>b），          a  b   c b        。
    public static int getGreatestCommonDivisor2(int numberA, int numberB) {
        int result = 1;
        if (numberA > numberB) {
            result = gcd2(numberA, numberB);
        } else {
            result = gcd2(numberB, numberA);
        }
        return result;
    }

    private static int gcd2(int a, int b) {
        if (a % b == 0) {
            return b;
        } else {
            return gcd2(b, a % b);
        }
    }

    //           a b（a>b），          a-b   c    b      
    public static int getGreatestCommonDivisor3(int numberA, int numberB) {
       if(numberA == numberB){
           return  numberA;
       }
        if (numberA < numberB) {
            return  getGreatestCommonDivisor3(numberB - numberA, numberA);
        } else {
            return  getGreatestCommonDivisor3(numberA - numberB, numberB);
        }
    }

    //          
    public static int getGreatestCommonDivisor4(int numberA, int numberB) {
        if(numberA == numberB){
            return  numberA;
        }
        if (numberA < numberB) {
            return  getGreatestCommonDivisor4(numberB, numberA);
        } else {
            boolean bA = (numberA & 1) == 1;
            boolean bB = (numberB & 1) == 1;
            if(!bA && !bB){
                return getGreatestCommonDivisor4(numberA>>1, numberB>>1) <<1;
            }else if(!bA && bB){
               return getGreatestCommonDivisor4(numberA>>1, numberB) ;
            }else if(bA && !bB){
               return getGreatestCommonDivisor4(numberA, numberB>>1);
            }else {
                return getGreatestCommonDivisor4(numberA, numberA - numberB);
            }
        }
    }

}

最後に、上記のすべての解法の時間的複雑さをまとめます.
1.暴力列挙法:時間の複雑さはO(min(a,b))
2.転がり相除算法:時間の複雑さは計算しにくく、O(log(min(a,b))に近似できるが、型取り演算性能は劣る.
3.更相減損術:型取り演算は避けたが、アルゴリズム性能は不安定で、最悪時間複雑度はO(max(a,b))
4.更相減損術とシフトの結合:型取り演算を避けるだけでなく、アルゴリズム性能が安定し、時間複雑度がO(log(max(a,b))))である.
具体的なアルゴリズム:aとbが共に偶数である場合、gcb(a,b)=2 gcb(a/2,b/2)=2 gcb(a>>1,b>>1)
aが偶数,bが奇数である場合,gcb(a,b)=gcb(a/2,b)=gcb(a>>1,b)
aが奇数,bが偶数のとき,gcb(a,b)=gcb(a,b/2)=gcb(a,b>>1)
aとbが共に奇数である場合、より相減損術により1回演算し、gcb(a,b)=gcb(b,a−b)である場合、a−bは必然的に偶数であり、シフト演算を継続することができる.