mathnumberstheorygreatest-common-divisor

Intuitive Understanding of GCD algorithm


What's an intuitive way to understand how this algorithm finds the GCD?

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

Solution

  • Wikipedia has a good article on it under the name Euclidean algorithm. In particular, this image from the article might answer your literal question: the intuitive way to understand how this algorithm finds GCD:

    Euclidean algorithm visualisation

    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.