**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

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

### Like this:

Like Loading...

*Related*

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