最大公约数

算法 2016-10-14

更相减损术

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

20161014092205.png

它的原理是:两个正整数a和b(a>b),它们的最大公约数等于a-b的差值c和较小数b的最大公约数。

//更相减损法
int gcd(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b -a;
    }
    return a;
}

当两数相差较大是,比如1和100000,那它就要循环99999次。

辗转相除法

辗转相除法, 又名欧几里得算法,它是已知最古老的算法。

20161014092727.png

这条算法基于一个定理:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

//辗转相除法
int gcd(int a, int b) {
    int c;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

通过取模让循环次数就得到保证,但当两个整数较大时,做a % b运算的性能比较低。

改进

其实是可以把上面两种的优势结合起来。对计算机来说,位运算的性能是非常快的。a和b(a>b)的最大公约数满足:

  • 当a和b是偶数时,gcd(a, b) = 2 * gcd(a/2, b/2)
  • 当a为偶数,b为奇数,gcb(a,b) = gcb(a/2, b)
  • 当a为奇数,b为偶数,gcb(a,b) = gcb(a, b/2)
  • 当a和b均为奇数,利用更相减损术运算一次,gcb(a,b) = gcb(b, a-b), 此时a-b必然是偶数,又可以继续进行移位运算。
    int gcd(int a, int b) {
    int i = 0;
    while (a != b) {
        if (!a&1 && !b&1) {
            a = a >> 1;
            b = b >> 1;
            ++i;
        }else if(!a&1 && b&1){
            a = a >> 1;
        }else if(a&1 && !b&1) {
            b = b >> 1;
        }else {
            if (a > b)
                a = a - b;
            else
                b = b - a;
        }
    }
    return a << i;
    }

    当两数越大,计算次数和时间的节省就越明显。


本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!