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.
Notes on Blackbody radiation
2 years ago
This comment has been removed by a blog administrator.
ReplyDelete