Extended Euclid

Fifnmar edited 4 年前

Extended Euclid

欧几里得算法是求最大公约数常用的递归算法。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

根据 Bézout’s Identity, 方程
$$
ax+by=\gcd(a, b)\tag1
$$
必有整数解。

思考通过使用递归来解决这个问题。

首先,base case 是 b == 0。此时,a 就是答案,而显然 $x = 1$ 且 $y = 0$。

然后,对 recursive cases,想办法把相关式变成和 $(1)$ 同形式的方程。

由于
$$
\begin{cases}\gcd(a, b) = \gcd(b, a\;\%\;b) \a\;\%\;b = a - \frac{a}{b}\times b\end{cases}
$$
所以
$$
\begin{align}bs + (a - \frac{a}{b}\times b)t &= \gcd(a, b)\at + b(s - \frac{a}{b}\times t) &= \gcd(a, b)\end{align}
$$
对比
$$
ax + by = gcd(a, b)
$$
可以对应得出:
$$
\begin {cases}x &= t\y &= s = \frac{a}{b}\times t\g &= g\end {cases} \tag2
$$
其中 $g$ 是最大公约数。

有人喜欢把递归过程对应的变量用同样的字母表示,如 $x’$。这里,我使用了两个不同的字母表示。但对应的关系是一致的。


声明函数:

ext_gcd(a, b) -> (gcd(a, b), x, y)
    where a, b, x and y are integral,
          a * x + b * y = gcd(a, b);

定义如下:

auto ext_gcd(int a, int b) -> tuple<int, int, int> {
    if (b == 0) {
        return {a, 1, 0};
    } else {
        auto [g, s, t] = ext_gcd(b, a % b);
        return {g, t, s - a / b * t}; // div b first, for it is modulus div.
    }
}

证明:$(2)$ 式最终收敛于 $b = 0$ 的 base case。

显然,这个函数的递归式 auto [g, s, t] = ext_gcd(b, a % b);gcd 相同,所以显然它和普通的 gcd 一样,都可以收敛到 $b=0$ 的情况。

Comments