Binary Euclid's Algorithm

Euclid's algorithm is tersely expressed by the recursive formula

(1)	gcd(N,M) = gcd(M, N mod M),

where (N mod M) is the remainder of division of N by M. We postulate gcd(N,0) = N in accordance with the end condition of Euclid's algorithm. Our example appears as

gcd(2322,654) = gcd(654,360) = gcd(360,294) = gcd(294,66) = gcd(66,30) = gcd(30,6) = gcd(6,0) = 6.

Other properties of gcd are expressed in such a similarly concise form

1. gcd(KN, KM) = K gcd(N, M)
2. If gcd(N,M) = 1 then gcd(N,MK) = gcd(N,K)
3. gcd(N, M) = gcd(N - M, M)

There are many ways to prove these. For instance, the first and second follow from the Fundamental Theorem of Arithmetic; the second (in a more direct manner) is also a consequence of a generalization of Proposition VII.30 the third one follows from the basic properties of modular arithmetic and division. A binary algorithm for finding gcd(N,M) is based on the following

1. If N and M are even, gcd(N, M) = 2 gcd(N/2, M/2),
2. If N is even while M is odd, then gcd(N, M) = gcd(N/2, M),
3. If both N and M are odd, then (since N-M is even) |N-M| < max(N,M). Replace the largest of the two with |N-M|.

The algorithm is known as binary because, unlike the original one, it does not use general division of integers but only division by 2. Since in a computer numbers are represented in the Binary system anyway, you should not be surprised to learn that there is a special machine instruction that implements division by 2 in a highly efficient manner. This is known as the right shift wherein the rightmost bit is discharged, the remaining bits are shifted one place to the right and the leftmost bit is set to 0.

Another handy operation is a bitwise conjunction &. N & 1 is either 1 or 0 for any integer N. It's 1 iff N is odd. Bitwise conjunction is also implemented in hardware, i.e., as a machine instruction.

The binary algorithm was discovered by R.Silver and J.Tersian in 1962 and has been published by G.Stein in 1967. Convergence of the algorithm, if not obvious, can be shown by induction. Property 3. above assures that induction is applicable.

Using our example:

N M Explanation Factor to Remember 2322 654 right shift N and M 2 1161 327 N - M 834 327 right shift N 417 327 N - M 90 327 right shift N 45 327 M - N 45 282 right shift M 45 141 M - N 45 96 right shift M 45 48 right shift M

N M Explanation Factor to Remember 45 24 right shift M 45 12 right shift M 45 6 right shift M 45 3 N - M 42 3 right shift N 21 3 N - M 18 3 right shift N 9 3 N - M 6 3 right shift N 3 3 N - M 0 3

The last non-zero term is 3 which, when combined with the saved factor 2, gives gcd(2322,654) = 6.

The algorithm is a slight improvement over the original method. What's most remarkable about it is that it's the first such improvement of Euclid's algorithm suggested in more than 2000 years.

References

1. D.Knuth, Seminumerical Algorithms, Addison-Wesley, 1969.

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Algorithm (An Interactive Illustration)
  • Euclid's Game
  • Extension of Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Lame's Theorem - First Application of Fibonacci Numbers
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny