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
      b = b-a
  Result is max(a,b) * 2shift

Log in or register to write something here or to contact authors.