使用 2 种欧几里德方法寻找 GCD 的复杂性

Question

我正在尝试使用两种方法找到两个数字的 gcd，一种是减法

    int gcd2(int a, int b)
{
    if (a == 0)
        return b;
    else
        printf("Iteration\n");

    if(a>=b)
    a=a-b;
    else
    b=b-a;

    return gcd2(min(a,b),max(a,b));
}

还有一种是模运算

    int gcd1(int a, int b)
{
    if (a == 0)
        return b;
    else
        printf("Iteration\n");
    return gcd1(b%a, a);
}

我知道 gcd2 中的迭代次数比 gcd1 多，但在 gcd1 中我使用的是模运算，这也很昂贵，所以我想知道这两种方法在运行时方面是否相同。

Answer 1

Knuth 在“计算机编程的艺术”第 2 卷第 4.5.2 节中广泛介绍了 gcd

他的二进制 gcd 版本更复杂，并使用了这些事实:

a) 如果u和v是偶数，gcd(u, v)=2gcd(u/2, v/2)

b) 如果 u 是偶数 v 是奇数，gcd(u, v) = gcd(u/2, v)

c) 与欧几里得算法一样，gcd(u, v) = gcd(u-v, v)

d) 如果 u 和 v 都是奇数，那么 u-v 是偶数并且 |u-v| < 最大值 (u, v).

对于他的模型计算机 MIX，二进制 gcd 比欧几里德 gcd 快大约 20%。您的里程可能会有所不同。