The greatest common divisor ( GCD ) of two integers a and b is usually calculated with the ( well-known ) Euclidean Algorithm. There is however an alternative algorithm which is based on an entirely different idea. Let's illustrate this idea with an example. Let a, b be integers, a >:b and (a, b) = GCD(a,b). Then the following rules can be applied recursively until a=b=GCD(a,b):

If ( a=even AND b=even) then GCD(a,b)=2*GCD(a/2,b/2)

If ( a=odd AND b=even) then GCD(a,b)=GCD(a,b/2)

If ( a=even AND b=odd) then GCD(a,b)=GCD(a/2,b)

If ( a=odd AND b=odd) then GCD(a,b)=GCD(a-b,b)

Example

(36, 27) = (27, 36/2)

(27, 18) = (27, 18/2)

(27, 9) = (27-9, 9)

(18, 9) = (18/2, 9)

(9, 9) Halt.

GCD(36,27)=9.

Compare using the Euclidean Algorithm

36 = 1 * 27 + 9

27 = 3 * 9 + 0 Halt.

GCD(36,27)=9.

However, this doesn't mean that the Euclidean Algorithm is always faster.

3 bloggers

1 week ago