Binary GCD

ALGORITHM

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

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
2. If U is even and V is odd, then
3. If U is odd and V is even, then
4. If U and V are both odd, then

EXAMPLE

We illustrate for .

Hence the result is

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