直观理解GCD算法

Question

理解此算法如何找到 GCD 的直观方法是什么？

function gcd(a, b) {
    while (a != b)
        if (a, b)
            a -= b;
        else
            b -= a;
    return a;
}

Answer 1

维基百科上有一篇名为 Euclidean algorithm 的好文章。特别是，文章中的这张图片可能会回答您的字面问题：理解该算法如何找到 GCD 的直观方法：

Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.

Answer 2

简而言之，如果 a 和 b 都可以被 D 整除，那么它必须是 a-b 的约数并且不能大于 a-b。逻辑是通过添加规则递归地应用此规则，即对于 a=b GCD 是 a:

GCD(a, b) = a == b ? a : GCD(min(a, b), abs(a-b))

Answer 3

最大公约数算法的最初发明者是 Euclid，他在基督诞生前大约 300 年在他的书 Elements 中描述了它。这是他的几何解释，包括他的图表：

Let AB and CD be the two given numbers not relatively prime.

It is required to find the greatest common measure of AB and CD.

If now CD measures AB, since it also measures itself, then CD is a common measure of CD and AB. And it is clear that it is also the greatest, for no greater number than CD measures CD.

But, if CD does not measure AB, then, when the less of the numbers AB and CD being continually subtracted from the greater, some number is left which measures the one before it.

For a unit is not left, otherwise AB and CD would be relatively prime, which is contrary to the hypothesis.

Therefore some number is left which measures the one before it.

Now let CD, measuring BE, leave EA less than itself, let EA, measuring DF, leave FC less than itself, and let CF measure AE.

Since then, CF measures AE, and AE measures DF, therefore CF also measures DF. But it measures itself, therefore it also measures the whole CD.

But CD measures BE, therefore CF also measures BE. And it also measures EA, therefore it measures the whole BA.

But it also measures CD, therefore CF measures AB and CD. Therefore CF is a common measure of AB and CD.

I say next that it is also the greatest.

If CF is not the greatest common measure of AB and CD, then some number G, which is greater than CF, measures the numbers AB and CD.

Now, since G measures CD, and CD measures BE, therefore G also measures BE. But it also measures the whole BA, therefore it measures the remainder AE.

But AE measures DF, therefore G also measures DF. And it measures the whole DC, therefore it also measures the remainder CF, that is, the greater measures the less, which is impossible.

Therefore no number which is greater than CF measures the numbers AB and CD. Therefore CF is the greatest common measure of AB and CD.

观察到欧几里得用词"measures"表示较小长度的某个倍数与较大长度相同；也就是说，他的概念 "measures" 与我们的概念 "divides" 相同，如 7 除 28.

直观理解GCD算法

Intuitive Understanding of GCD algorithm

theory

math

numbers

greatest-common-divisor