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
### (uses only masks, shifts and adds)
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.

Advertisements

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


%d bloggers like this: