​求两个整数的最大公约数，最优算法？

求两个整数的最大公约数，要尽量优化算法的性能。

暴力枚举法 version_1

#include
#include
using namespace std;

int GreatestCommonDivisor(int num1, int num2) {
    if (num1 <= 0 || num2 <= 0) {
        return -1;
    }
    int big = num1 > num2 ? num1 : num2;
    int small = num1 < num2 ? num1 : num2;

    if (big % small == 0) {
        return small;
    }

    for (int i = small / 2; i > 0; --i)
    {
        if (big % i == 0 && small % i == 0) {
            return i;
        }
    }
    return 1;
}


int main(int argc, char const* argv[])
{
    assert(GreatestCommonDivisor(10, 5) == 5);
    assert(GreatestCommonDivisor(25, 10) == 5);
    assert(GreatestCommonDivisor(255, 3) == 3);
    assert(GreatestCommonDivisor(2, 3) == 1);
    assert(GreatestCommonDivisor(20000, 2) == 2);
    assert(GreatestCommonDivisor(100, 75) == 25);
    assert(GreatestCommonDivisor(99, 55) == 11);
    return 0;
}

暴力枚举，从较小整数的一半开始，试图找到一个合适的数，判断是否能被这两个数整除。

虽然这个方法实现了所有的功能，但是效率不太行啊。

辗转相除法，又名欧几里得算法（Euclidean algorithm），该算法的目的是求出两个正整数的最大公约数。它是已知最古老的算法，其产生时间可追溯至公元前300年。

a, b(a > b) 的最大公约数等于 (a % b = c), b 和 c 的最大公约数

辗转相除法 version_2

#include
#include
using namespace std;

int GreatestCommonDivisor(int num1, int num2) {
    if (num1 <= 0 || num2 <= 0) {
        return -1;
    }
    int big = num1 > num2 ? num1 : num2;
    int small = num1 < num2 ? num1 : num2;

    if (big % small == 0) {
        return small;
    }

    return GreatestCommonDivisor(big % small, small);
}


int main(int argc, char const *argv[])
{
    assert(GreatestCommonDivisor(10, 5) == 5);
    assert(GreatestCommonDivisor(25, 10) == 5);
    assert(GreatestCommonDivisor(255, 3) == 3);
    assert(GreatestCommonDivisor(2, 3) == 1);
    assert(GreatestCommonDivisor(20000, 2) == 2);
    assert(GreatestCommonDivisor(100, 75) == 25);
    assert(GreatestCommonDivisor(99, 55) == 11);
    return 0;
}

辗转相除法相对于暴力枚举已经好了很多了，还有一个问题，当整数较大时，求余的性能比较差。

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

两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和b的最大公约数。

更相减损术 version_3

#include
#include
using namespace std;

int GreatestCommonDivisor(int num1, int num2) {
    if (num1 <= 0 || num2 <= 0) {
        return -1;
    }
    int big = num1 > num2 ? num1 : num2;
    int small = num1 < num2 ? num1 : num2;

    if (big - small == 0) {
        return small;
    }

    return GreatestCommonDivisor(big - small, small);
}


int main(int argc, char const* argv[])
{
    assert(GreatestCommonDivisor(10, 5) == 5);
    assert(GreatestCommonDivisor(25, 10) == 5);
    assert(GreatestCommonDivisor(255, 3) == 3);
    assert(GreatestCommonDivisor(2, 3) == 1);
    assert(GreatestCommonDivisor(20000, 2) == 2);
    assert(GreatestCommonDivisor(100, 75) == 25);
    assert(GreatestCommonDivisor(99, 55) == 11);
    return 0;
}

更相减损术，避免了大整数取模可能出现的性能问题，但是当两数相差很大时，递归次数也很大。

辗转相除法结合更相减损术 version_4

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

#include
#include
using namespace std;

int GreatestCommonDivisor(int num1, int num2) {
    if (num1 <= 0 || num2 <= 0) {
        return -1;
    }
    int big = num1 > num2 ? num1 : num2;
    int small = num1 < num2 ? num1 : num2;

    if (big - small == 0) {
        return small;
    }

    if ( (big & 1) == 0 && (small & 1) == 0) {
     // 当两数均为偶数时
        return GreatestCommonDivisor(big >> 1, small >> 1) << 1;

    } else if ( (big & 1) != 0 && (small & 1) != 0) {
     // 当两数均为奇数时，两数相减必是偶数，运用更相减损术
        return GreatestCommonDivisor(big - small, small);

    } else if ( (big & 1) == 0) {
     // 当较大的数是偶数时
        return GreatestCommonDivisor(big >> 1, small);

    } else {
     // 当较小的数是偶数时
        return GreatestCommonDivisor(big, small >> 1);
    }

    return 1;
}


int main(int argc, char const *argv[])
{
    assert(GreatestCommonDivisor(10, 5) == 5);
    assert(GreatestCommonDivisor(25, 10) == 5);
    assert(GreatestCommonDivisor(255, 3) == 3);
    assert(GreatestCommonDivisor(2, 3) == 1);
    assert(GreatestCommonDivisor(20000, 2) == 2);
    assert(GreatestCommonDivisor(100, 75) == 25);
    assert(GreatestCommonDivisor(99, 55) == 11);
    return 0;
}

这种方式在两数都比较小时，可能看不出计算次数的优势；当两数越大时，计算次数的减少就会越明显。