辗转相除法与更相减损术

前言：辗转相除法与更相减损术

概述

辗转相除法与更相减损术的原理是相同的

辗转相除法：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数

更相减损术：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数

辗转相除法

// 注意，如果b > a，此算法的第一次循环会将a b交换。
public gcd(int a,int b)
{
    int r = a % b;
    while(r > 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

缺点:两个数字大时，取模慢

更相减损术

public int gcd(int a,int b) {
    while(a != b) {
    	if(a > b){
    	    a = a - b;
        }
    	else{
    	    b = b - a;
    	}
    }
    return a;
}

缺点：两数相差大时，需要非常多次相减

两者结合

众所周知，移位运算的性能非常快。对于给定的正整数a和b，不难得到如下的结论。其中gcb(a,b)的意思是a,b的最大公约数函数：

当a和b均为偶数，gcb(a,b) = 2gcb(a/2, b/2) = 2gcb(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均为奇数，利用更相减损术运算一次，gcb(a,b) = gcb(b, a-b)，

此时a-b必然是偶数，又可以继续进行移位运算

比如计算10和25的最大公约数的步骤如下：

1. 整数10通过移位，可以转换成求5和25的最大公约数利用更相减损法，
2. 计算出25-5=20，转换成求5和20的最大公约数
3. 整数20通过移位，可以转换成求5和10的最大公约数
4. 数整数10通过移位，可以转换成求5和5的最大公约数
5. 利用更相减损法，因为两数相等，所以最大公约数是5

在两数比较小的时候，暂时看不出计算次数的优势，当两数越大，计算次数的节省就越明显。

代码

注：位与运算符（&）,如果两个数都为1则为1，否则为0

public int gcd(int a, int b) {
    if (a == b) {
        return a;
    }
    if (a < b) {
        return gcd(b, a);
    } else {
        if ((a & 1) == 0 && (b & 1) == 0) {
            return gcd(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            return gcd(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            return gcd(a, b >> 1);
        } else {
            return gcd(a, a - b);
        }
    }
}