Euclid's GCD

Return to List of Derive functions

Euclid's Greatest Common Divisor (GCD).

Derive has an efficient internal function GCD(m,n,p,q,...), where m,n,p,q,... are any number of arguments. So

GCD(32, 8, 16, 4, 2)

simplifies to

If we consider the general Euclidean algorithm for gcd, using two real numbers, what is the largest number that divides exactly into both?

Divide the larger number by the smaller number

The new pair of numbers now becomes the smaller of the two previous numbers, and the remainder of the division

Repeat the division of the larger number by the smaller number

Continue this process until there is no remainder

The Greatest Common Divisor is the number that pairs with the last zero-producing division.

In Derive code:

euclid(x, y, z) :=
    Loop
    If y = 0
      RETURN ABS(x)
    z := MOD(x, y)
    x := y
    y := z

In Derive's Entry bar, this is typed as:

euclid(x, y, z) := LOOP(IF(y = 0, RETURN ABS(x)), z := MOD(x, y), x := y, y := z)

we suggest you copy and paste it from here.

So:

euclid(234,-789)

Want a 'test tip'?