The Euclidean Algorithm

Algorithm from ancient world.

Photo by Cristina Gottardi on Unsplash

In this lesson, we will talk about an old algorithm that is used nowadays as a cornerstone in many areas of computer science that depends on computing efficiently the greatest common divisor of two numbers.

Before discussing the approaches to get it we need to know what is the greatest common divisor.

Let us consider two bars red bar and a blue bar where the red bar is larger than the blue one. The largest common divisor of these two bars is the largest possible common length of the two bars.

Greatest Common Divisor example

We have two approaches to finding the greatest common divisor of two numbers:

1- Slow approach

2- Euclidean approach

The slow approach is too simple all you have to do is subtract the bigger bar from the smallest bar and assign the result to the biggest one until the two bars are equal and then you have the greatest common divisor.

function slowApproach(num1,num2){
    while(num1 !== num2){
        if(num1 > num2){
        num1-=num2
        }
        else{
         num2-=num1
        }
    }
    return `The greatest common divisor is ${num1}`
}

console.log(slowApproach(21,15))

The problem with this approach is that if num1 is much bigger than num2, we will do many iterations to make them equal, for example, if num1 = 1001 and num2 = 2.
Then we will nearly make 500 iterations until num1 become below 2 and we can easily get this number by dividing 1001 by 2 and it will nearly give you 500.
The fun fact is that the Euclidean approach which is faster depends on what we conclude let us discuss it in the next part.

The faster Euclidean approach depends on dividing the two numbers and making the second one take the remainder of this division.

If we consider the previous example in which num1 = 1001 and num2 = 2 and we divide both of them and approximate it we get 500 if we multiply it by 2 we get 1000 and the remainder will be 1001-1000 which will be 1

The equation will be as follows:

num1 = q * num2 + r (remainder)

1001 = 500 * 2 + 1

num2 will take the remainder as we said above so it will be 2 and num1 will be equal num2 so it will be 2.

As you can notice we are so close to reaching the greatest common divisor with only one step if we have to use a slow approach to reach the same point we will need 500 steps.

Now num1 = 2 and num2 = 1 what to do next will be the same thing divide num1 by num2 you will get 2 and our equation will be as follows:

2 = 2 * 1 + 0

The remainder now is zero so num2 becomes 0 when reaching this case then we can stop looping and return num1 which will equal the previous value of num2 which is 1 and we finally have the greatest common divisor in only two steps.

So this algorithm is faster and the maximum iterations it will need is the total number of digits of the two numbers passed. Considering our example it will be 5 iterations only at max.

function euclideanAlgorithm(num1,num2) {
    //Ensure that always first num is bigger
    if(num1 < num2){
        let temp = num1;
        num2 = num1;
        num1 = temp;
    }
    while(num2 !== 0){
        let q = Math.floor(num1 / num2) 
        let r = num1 - (q*num2)
        num1 = num2
        num2 = r   
    }
    
   return `The greatest common divisor is ${num1}`
}

console.log(euclideanAlgorithm(1001,2))

The faster approach is not too complex as you can see the code is also simple but it’s the power of the Math that make us achieve this great approach which is more efficient and faster.

That was another lesson explained from the Algorithms Unplugged Book. It was lesson number 2 in part 2 (Arithemtic and Encryption) Looking forward for more lessons explained in this book then follow me.