User:Jarhill/Euclidan algorithm

Implementations

Implementations of the algorithm may be expressed in pseudocode. For example, the division-based version may be programmed as

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

At the beginning of the kth iteration, the variable b holds the latest remainder r_k−1, whereas the variable a holds its predecessor, r_k−2. The step b := a mod b is equivalent to the above recursion formula r_k ≡ r_k−2 mod r_k−1. The temporary variable t holds the value of r_k−1 while the next remainder r_k is being calculated. At the end of the loop iteration, the variable b holds the remainder r_k, whereas the variable a holds its predecessor, r_k−1.

In the subtraction-based version which was Euclid's original version, the remainder calculation (b := a mod b) is replaced by repeated subtraction. Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when a = b:

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

The variables a and b alternate holding the previous remainders r_k−1 and r_k−2. Assume that a is larger than b at the beginning of an iteration; then a equals r_k−2, since r_k−2 > r_k−1. During the loop iteration, a is reduced by multiples of the previous remainder b until a is smaller than b. Then a is the next remainder r_k. Then b is reduced by multiples of a until it is again smaller than a, giving the next remainder r_k+1, and so on.

The recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd(r_N−1, 0) = r_N−1.

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

For illustration, the gcd(1071, 462) is calculated from the equivalent gcd(462, 1071 mod 462) = gcd(462, 147). The latter GCD is calculated from the gcd(147, 462 mod 147) = gcd(147, 21), which in turn is calculated from the gcd(21, 147 mod 21) = gcd(21, 0) = 21.