Greatest common divisor for 2 integers | Algorithm in C++

 Algorithm for finding greatest common divisor of two positive integers

Greatest common divisor is the greatest integer which divides both the given positive integers discretely or exactly. I am going to use a version of the Euclid algorithm described in his book Euclid's Elements. The algorithms have been written in the C++ language. The algorithm adapted here used to be one of the most well-known algorithms in the 1950's and one of the first to have the word "algorithm" associated with it. One can find implementations of this algorithm which use recursive functions as well. Here, I have developed a process using the most basic of programming concepts. 

This algorithm has a finite number of steps before it terminates( when the remainder becomes zero). It takes in two inputs ("m" and "n") and gives out one output (GCD in the form of "n"). 

In this example, one can also notice how the do-while loop is better suited to certain situations than the more popular while loop.

Using the while loop:

The code:

#include <iostream>
using namespace std;

int main()
{
    int m = 15, n = 65;                 //two inputs
    int r = -1;                         //remainder assigned an arbitrary value to make while loop 
                                        //condition come true
                                        
    while(r != 0){                      // if remainder is not zero continue into the while loop body
        r = m % n;                      //compute remainder
        if(r == 0){
           cout<<"GCD is: "<<n;         //if remainder is zero, present n as GCD
        }
        m = n;                          // assignment operations on variables
        n = r;
    }
}

The above code requires one to set the value of the remainder "r" as an arbitrary integer(-1 in this case) before the body of the while loop. Such a requirement can be avoided with the use of a do-while loop instead of a while loop. This more elegant solution is described below.

Using the do-while loop:

The code:

#include <iostream>
using namespace std;

int main()
{
    int m = 15, n = 65;                    //two inputs
    int r;                                 //remainder

    do{                                    //step 2
        r = m % n;                         //compute remainder
        if(r == 0){
           cout<<"GCD is: "<<n;            //if remainder is zero, present n as GCD
        }
        m = n;                             // assignment operations on variables
        n = r;                             
    } while(r != 0);                       // if remainder is not zero, go to step 2 
}

In the above code, there is no arbitrary assignment to remainder "r". Therefore, the code is easier to understand.

Now let us look into the various components of the program and how they interact with one another.

The two positive integers whose GCD is to be found are represented by "m" and "n" in the code. The variable "r" represents the remainder of the division m / n. 

The algorithm proceeds as follows:

1. Find the remainder of the division m / n (using m% n) and assign it to "r".
2. Check if the value of "r" is equal to zero. If it is true, print "n" as the answer (GCD). If it isn't proceed ahead.
3. Assign the value of "n" to "m" and then the value of "r" to "n". Return to Step 1 if "r" is not zero.

As soon as the variable "r" becomes zero the GCD has been obtained in the variable "n." 

The output of both programs is:

    The algorithm can be visualized like this:

The value of "n" once "r" has become zero is presented as GCD.