又来盘点最大公约数的算法👩

你媽的，为什么又双叒叕开学了！假期，你不要停下来啊！

嘛，第一节课是算法设计与分析课，郑某人带的学生由原来的俺们整个软工三个班换成原来俺们一个班和计嵌软嵌了。首先呢，郑某人自我介绍了一下：”我是普通老师郑玉！”，嗯，普通市民刘青云？还是普通家庭马化腾？

开学第一节课就讲最大公约数(greatest common divisor,简写为gcd)，老师要是不说我差点儿就忘了，俺就趁下课时间温习一下我遇到过的几个最大公约数的算法。

来来来，先总结一下本文所有解法的时间复杂度：

暴力枚举法：时间复杂度是 O(min(a, b)))
辗转相除法：时间复杂度不太好计算，可以近似为 O(log(max(a, b)))，但是取模运算性能较差。
更相减损术：避免了取模运算，但是算法性能不稳定，最坏时间复杂度为 O(max(a, b)))
Stein算法：不但避免了取模运算，而且算法性能稳定，时间复杂度为 O(log(max(a, b)))

暴力枚举法

蛤蛤蛤，一听名字就知道这很暴力了，最耗时间，时间复杂度是 O(min(a, b)))。

const gcd = (a, b) => {
    const small = a < b ?a:b, big = a >= b ?a:b;
    if(big%small==0) return small;

    let res = 1;
    for(const i=2;i<=small/2; ++i)
        if(a%i==0 && b%i==0)
            res = i;
    return res;
}

使用暴力枚举的方法，试图寻找到一个合适的整数 i，看看这个整数能否被两个整型参数 numberA 和 numberB 同时整除。

这个整数 i 从2开始循环累加，一直累加到 numberA 和 numberB 中较小参数的一半为止，在循环中一直不断寻找能够被两数同时整除的最大 i 值。循环结束后最终得到的就是两数的最大公约数。

性能分析：传入两个参数10000或10001，那么就需要计算10000/2-1=4999次。✨

辗转相除法

辗转相除法，又名欧几里得算法（Euclidean algorithm），目的是求出两个正整数的最大公约数。它是已知最古老的算法，其可追溯至公元前300年前。
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25，25除以10商2余5,那么10和25的最大公约数，等同于10和5的最大公约数。

一言以蔽之就是 两数a>b, 结果就是 gcd(较小数, 余数)，简单吧？

俺搜集了一堆算法👇（注：以下算法为了简洁就没有放大小判断，请保证a>b）

//递归实现
const gcd = (a, b) => {
    if(!b) return a;
    return gcd(b, a%b);
}
//上面算法的简写
const gcd = (a, b) => b == 0 ? a : gcd(b,a%b); 
//迭代实现
const gcd = (a, b) => {
    int c = a%b;
    while(c){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}
//用到了位运算
const gcd = (a, b) => {  
    while(b)  
    {  
        a%=b;  
        b^=a; //这样写就是上面的分部写法  
        a^=b; //因为不这样写的话是会引起错误的，好像叫未定义行为  
        b^=a; //而分部写的话就不会出现这种错误  
    }  
    return a;  
}
//(慎用)上面算法的简写
const gcd = (a, b) => {   
{  
    while(b^=a^=b^=a%=b); //这样写是不正确的，因为这样写在不同的语言下又可能结果不同
    return a; //这样写的格式是我从百度上看到的，思路和辗转相除一样，不是正确的完整写法
}

再来个充分利用ES6语法的超骚写法，摘自 30 seconds of code：

const gcd = (...arr) => {
  const _gcd = (x, y) => (!y ? x : gcd(y, x % y));
  return [...arr].reduce((a, b) => _gcd(a, b));
};

Example:

1 2	gcd(8, 36); // 4 gcd(...[12, 8, 32]); // 4

所以我们可以看到，辗转相除法的核心就是那个取余了对不对？

欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。然而它有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。

那有没有什么办法能抛弃除法和取余呢？👇

更相减损术

更相减损术，出自于中国古代的《九章算术》，也是一种求最大公约数的算法。

他的原理更加简单：两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25，25减去10的差是15,那么10和25的最大公约数，等同于10和15的最大公约数。

换言之就是，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以相等为止，最大公约数就是最终相等的两个数。

一言以蔽之就是 两数a>b，gcd(差值, 较小数)。

const gcd = (a, b) => {
    if(a == b) return a;
    if(a < b) return gcd(b-a,a);
    else return gcd(a-b,b);
}
//迭代解法
const gcd = (a, b) => {
    while(a!=b)
        if(a>b) a-=b;  
        else b-=a;
    return a;  
}
//当然递归也可以这么写，无非就是循环次数不一样
const gcd = (a, b) => {
    if (y == 0) return x;
    if (x < y) return gcd(y, x);  
    else return gcd(x - y, y);  
}

更相减损术避免了大整数取余带来的性能问题，然而其按照求差的方式计算，将导致运算次数大大增加。

比如当两数悬殊是10000和1时，就要递归9999次。因此更相减损术是一种不稳定算法。

那有没有更好的算法既能规避取余又能保持较少的运算次数呢？👇

Stein算法

Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法算法不同的是，Stein算法只有整数的移位和加减法

把辗转相除法和更相减损术的优势结合起来，在更相减损术的基础上使用移位。

众所周知，移位运算的性能非常快。对于给定的正整数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均为奇数，利用更相减损术运算一次，gcb(a,b) = gcb(b, a-b)，此时a-b必然是偶数，又可以继续进行移位运算。

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

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

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

//我的写法，看起来还算直观
const gcd = (a, b) => {
    if(b==0) return a;
    if(areturn gcd(b,a);
    const isEven = (x) => x&1 == 0; // &1 就等效为 %2 啦
    if(isEven(a)) //分成了奇偶两种情况
        if(isEven(b)) return gcd(b,a-b);
        else return gcd(a,b>>1);
    else
        if(isEven(b)) return gcd(a>>1,b);
        else return 2*gcd(a>>1,b>>1);
}
//或者这样写，网上看到的
const gcd = (a, b) => {
    if(a == b) return a;
    if(a < b) return gcd(b, a); // 保证参数a永远大于参数b，可减少代码量
    else { // &1相当于%2,>>1相当于/2
        if(!a&1 && !b&1) return gcd(a>>1,b>>1)<<1;
        else if(!a&1 && b&1) return gcd(a>>1,b);
        else if(a&1 && !b&1) return gcd(a,b>>1);
        else return gcd(a,a-b);
    }
}