HCF without Division

The previous blog entry reminded me of this…

Many of you will be familiar with the Euclidean algorithm for calculating the HCF (highest common factor, also known as GCD, greatest common divisor). The algorithm is reasonably efficient, as it needs to enumerate the factors of neither of its arguments to find the product of their common factors. This algorithm does, however, make heavy use of division, which can be slow.

There is an alternative.

Firstly, as a reminder, here’s the better-known, and simpler, algorithm (in Python):

```### Euclidean algorithm (recursive version)
def hcf_Euclidean_recursive (a, b):
if b == 0:
return abs(a)
else:
return hcf (b, a % b)
### nb: this is just a swap if |a| < |b|```

Now, here’s an efficient, faster, division-free algorithm:

```### binary, division-free algorithm
def hcf_binary (a, b):
### special case
if (a == 0) and (b == 0):
return 0
a = abs (a)
b = abs (b)
### first find all common 2 factors
twos = 0
while (a & 1 == 0) and (b & 1 == 0):
twos += 1 ### ++ twos
a >>= 1
b >>= 1
### next, find remaining 2-free common factor
while (a != 0) and (b != 0):
while (a & 1 == 0):
a >>= 1
while (b & 1 == 0):
b >>= 1
### a and b now both odd
if a < b:
b = (b - a) >> 1
else:
a = (a - b) >> 1
### either a or b is now zero
return (a | b) << twos```

The latter algorithm might be a little more efficient than the former in virtue of being iterative rather than recursive, although that’s arguable with modern optimising compilers handling tail-recursion; but that’s not the point. The significant improvement that might be achieved comes from the lack of any division; instead, we have bitwise operations and subtractions. The number of steps required by each algorithm has about the same complexity: logarithmic in the input values, or linear in the bit-lengths of the inputs.