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) * 2^{shift}