# 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).

## 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).