Binary GCD

binary-gcd

ALGORITHM

It is well known that the Euclidean algorithm for the greatest common divisor can be expressed by the recursive formula

\gcd ( U , V ) = \gcd ( V , U \mod V )

Another algorithm, published by Stein in 1967, uses only multiplication and division by 2. It can be described as follows

  1. If U and V are both even, then \gcd(U,V) = 2 \gcd(U/2,V/2)
  2. If U is even and V is odd, then \gcd(U,V) = \gcd(U/2,V)
  3. If U is odd and V is even, then \gcd(U,V) = \gcd(U,V/2)
  4. If U and V are both odd, then \gcd(U,V) = \gcd(|U-V|/2,\min(U,V))

EXAMPLE

We illustrate for \gcd ( 12 , 18 ).

\gcd ( 12 , 18 ) = 2 \gcd ( 6 , 9 )

\gcd ( 6 , 9 ) = \gcd ( 3 , 9 )

\gcd ( 3 , 9 ) = \gcd ( 6 , 3 )

\gcd ( 6 , 3 ) = \gcd ( 3 , 3 )

Hence the result is 2 \cdot 3 = 6

PERFORMANCE

In practice, computers compute in binary form and the binary GCD algorithm can provide better results in average than the Euclidean algorithm (in bit operations). However, this performance should be considered with some caution since modern computers implement operations on several bits in a very efficient way.

A complete analysis of the binary GCD algorithm was established by Brigitte Vallée (Université de Caen, France).

Advertisements

One thought on “Binary GCD

  1. “use only multiplication and division” – and subtraction. It’s more important than it seems (for example in implementing gcd for binary numbers).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s