How the Euclidean Algorithm Works – with Code Examples in Go

The Euclidean Algorithm is a well-known and efficient method for finding the greatest common divisor (GCD) of two integers. The GCD is the largest number that can divide both integers without leaving a remainder.

The algorithm is named after the ancient Greek mathematician Euclid, who presented it in his book "Elements" around 300 BCE.

You can use this algorithm to solve Diophantine equations, to tackle the shortest-vector problem which is the foundation of lattice-based cryptography, and also to detect common patterns of pixels in images. This is, among other things, applied to optimize rendering processes and detect different objects in images.

How Does the Euclidean Algorithm Work?

Here's a step-by-step explanation of how the Euclidean Algorithm works:

Start with two positive integers, a and b, where a >= b. If a < b, simply swap their values. Note that this is meant for a convenient mathematical demonstration, as the implementation also works for a < b.

Divide a by b and find the remainder, r (use the modulo operation, represented as a % b). If r is 0, the GCD is b, and the algorithm terminates.

If r is not 0, set a to b and b to r. Then, repeat step 2.

The algorithm continues to iterate until the remainder is 0. At that point, the last non-zero remainder is the GCD of the original two numbers.

The Euclidean Algorithm works because the GCD of two numbers remains unchanged when the larger number is replaced by its remainder when divided by the smaller number.

Example of Euclidean Algorithm

Here's an example to illustrate the algorithm:

Let's find the GCD of 30 and 9:

a = 30, b = 9

Calculate the remainder: r = a % b = 30 % 9 = 3 (since 3 is not 0, continue to step 3)

Update the values: a = 9, b = 3

Calculate the new remainder: r = a % b = 9 % 3 = 0 (r is now 0)

The GCD of 30 and 9 is 3.

Why Does the Euclidean Algorithm Work?

The greatest common divisor of two integers is the largest positive integer that divides both of them without leaving a remainder. So the algorithm is based on the following key property:

If a and b are two integers, then the GCD of a and b is the same as the GCD of b and a % b, where % represents the modulo operator (the remainder after division).

Mathematically, the key property of the algorithm can be justified using the division algorithm:

Let a and b be two positive integers, such that a >= b. We can write the division algorithm as:

a = bq + r, where q is the quotient and r is the remainder.

Now, let d be a common divisor of a and b. Then, a = d * m1 and b = d * m2 for some integers m1 and m2. We can rewrite the division algorithm as:

d * m1 = (d * m2) * q + r.

Rearranging the equation, we get:

r = d * (m1 - m2 * q).

Since d is a factor of both a and b, and r can also be written as a multiple of d, we can conclude that d is also a divisor of r. This means that the GCD of a and b is also a divisor of r. So, we can replace b with r and keep finding the GCD using this algorithm until b becomes 0.

The Euclidean Algorithm is particularly useful due to its efficiency and simplicity, making it easy to implement in computer algorithms and programming languages.

Let's see some different ways to implement it in Go:

Recursive Implementation of the Euclidean Algorithm in Go

This implementation of the Euclidean Algorithm in Golang is a recursive version that finds the GCD of two integers. Let's go through it step by step:

The function is defined as GCD(a, b int) int. It takes two integer inputs, a and b, and returns an integer output.

The base case of the recursion is checked with if b == 0. If b is 0, the function returns the value of a as the GCD.

If b is not 0, a temporary variable tmp is created and assigned the value of a. This temporary variable is used to store the value of a before updating its value in the next step.

The values of a and b are updated as follows:

a is assigned the current value of b.
b is assigned the value of the remainder when tmp (the previous value of a) is divided by the new value of a (which was b before the update).

The function calls itself recursively with the updated values of a and b as input, return GCD(a, b).

The algorithm continues to call itself recursively until the base case is reached, that is b becomes 0. At this point, the function returns the GCD, which is the value of a.

// Recursive approach:
func GCD(a, b int) int {
	if b == 0 {
		return a
	}
	tmp := a
	a = b
	b = tmp % a
	return GCD(a, b)
}

For example, let's say we want to find the GCD of 56 and 48:

First call: GCD(56, 48)

Since b (48) is not 0, update a and b:
a becomes 48
b becomes 56 % 48 = 8
The function calls itself with the new values: GCD(48, 8)

Second call: GCD(48, 8)

Since b (8) is not 0, update a and b:
a becomes 8
b becomes 48 % 8 = 0
The function calls itself with the new values: GCD(8, 0)

Third call: GCD(8, 0)

Now, b (0) is 0, so the function returns a (8) as the GCD.

Iterative Implementation of the Euclidean Algorithm in Go

This implementation of the Euclidean Algorithm in Golang is an iterative version using a loop to find the GCD of two integers. Let's go through the code step by step:

The function is defined as GCD(a, b int) int. It takes two integer inputs, a and b, and returns an integer output.

A loop is used to iterate as long as b is not equal to 0. The loop condition is b != 0. Note that this for loop construction in Go is essentially a while loop in many other languages.

Inside the loop, the values of a and b are updated simultaneously using a tuple assignment: a, b = b, a%b. This line does the following:

a is assigned the current value of b.
b is assigned the value of the remainder when a is divided by b.

When the loop exits (that is, b becomes 0), the value of a is returned as the GCD.

The algorithm iterates until the remainder (b) is 0, at which point the GCD is the last non-zero remainder, which is the value of a.

func GCD(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

For example, let's say we want to find the GCD of 100 and 64:

Initialize a as 100 and b as 64. Check the loop condition: b (64) is not 0.