Course: JavaScript

Progress (0%)

  1. Foundation

  2. Numbers

  3. Strings

  4. Conditions

  5. Loops

  6. Arrays

  7. Functions

  8. Objects

  9. Exceptions

  10. HTML DOM

  11. CSSOM

  12. Events

  13. Drag and Drop

  14. opt Touch Events

  15. Misc

  16. Project: Analog Clock

Exercise: Euclidean Algorithm

Exercise 36 Easy

Prerequisites for the exercise

  1. JavaScript Function Recursions
  2. All previous chapters

Objective

Create a recursive function to implement the Euclidean algorithm.

Description

Thousands of years back, an extremely ingenious method was devised to find the greatest common divisor of two integers by the great Greek mathematician, Euclid. Today, it's commonly known as the Euclidean algorithm.

The method goes as follows:

Consider two positive integers ::a:: and ::b::. Let ::r_1 = a:: and ::r_2 = b::. The greatest common divisor of ::a:: and ::b::, denoted as ::\text{gcd}(a, b)::, can likewise also be expressed as ::\text{gcd}(r_1, r_2)::.

To find ::\text{gcd}(r_1, r_2)::, we apply the rule,

::\text{gcd}(r_1, r_2) = \text{gcd}(r_2, r_3)::

where ::r_3 = r_1 \bmod r_2:: (i.e. the remainder when ::r_1:: is divided by ::r_2::).

Similarly,

::\text{gcd}(r_2, r_3) = \text{gcd}(r_3, r_4)::

where ::r_4 = r_2 \bmod r_3:: (i.e. the remainder when ::r_2:: is divided by ::r_3::).

This goes on until ::r_{i + 1}:: in ::\text{gcd}(r_i, r_{i + 1}):: becomes equal to ::0::. At that point, the greatest common divisor becomes equal to ::r_i::. That is:

::\text{gcd}(r_i, r_{i + 1}) = \text{gcd}(r_i, 0) = r_i::

Thus, the answer to the original question, of finding ::\text{gcd}(a, b)::, becomes ::r_i::.

Let's consider an example.

Suppose we want to find ::\text{gcd}(104, 16)::. Since ::104 \bmod 16 = 8::, ::\text{gcd}(104, 16) = \text{gcd}(16, 8)::. Next, since ::16 \bmod 8 = 0::, ::\text{gcd}(16, 8) = \text{gcd}(8, 0)::. And finally, ::\text{gcd}(8, 0) = 8::. Ultimately, ::\text{gcd}(104, 16) = 8::.

The best thing about the Euclidean algorithm is that each subsequent computation is smaller than the previous one. Thus, it's guaranteed that we'll eventually get to a termination point.

That exactly why Euclidean algorithm works is out of the scope of this exercise. The good news is that the proof is extremely elementary, relying on the very basic ideas from number theory and naive set theory.

Anyways, in this exercise, you have to create a function gcd() to compute the greatest common divisor of two positive integers using the aforementioned Euclidean algorithm.

You shall assume that the provided arguments are valid integers. There is no need to implement an argument-validation mechanism (though, if you want to you could).

Note that your solution MUST use recursion, NOT iteration.

View Solution

New file

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-36-Euclidean-Algorithm and put the .html solution files for this exercise within it.

Solution

As stated in the description above, if the second argument to gcd(a, b) is 0, the greatest common divisor is simply a. Otherwise, the gcd is the value of gcd(a, a % b).

This is accomplished below:

function gcd(a, b) {
   if (b === 0) {
      return a;
   }
   else {
      return gcd(b, a % b);
   }
}

Note that another way to accomplish the same idea above is to stop right when a % b is 0 instead of passing that 0 value to gcd().

The code below illustrates this approach:

function gcd(a, b) {
   var r = a % b;
   if (r === 0) {
      return b;
   }
   else {
      return gcd(b, r);
   }
}

The variable r is created in order to prevent repeating the expression a % b twice, first in the if conditional and then in the second return statement.