A variation on Euclid's algorithm for computing a greatest common divisor which is better suited for a binary computer.
Note that the following hold:
gcd(2a,2b) = 2 gcd(a,b)
gcd(2a,2b+1) = gcd(a, 2b+1)
gcd(2a+1,2b+1) = gcd(2a-2b, 2b+1)
(and, of course, gcd(a,b)=gcd(b,a). This is enough to produce a very fast
GCD algorithm which uses only
binary operations (
AND and
right shift, mainly).
Binary GCD algorithm pseudocode
Initialise shift to 0.
While a > 0 and b > 0:
If a is even and b is even:
a = a/2, b = b/2, and increment shift
Else if a is even:
a = a/2
Else if b is even:
b = b/2
Else if a > b:
a = a-b
Else
b = b-a
Result is max(a,b) * 2shift