Implementing basic Mathematical operations (Euclidean algorithm for GCD)

Problem

Given two non-negative integers a and b, you’ve to find the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of the two numbers. In other words, find the largest number that divides them both.

Euclidean Algorithm

The Euclidean algorithm is one of the oldest numerical algorithms to compute the greatest common divisor (gcd) of two positive integers. The algorithm is based on the observation that the GCD of two numbers remains the same if the smaller number is subtracted from the larger number.
The algorithm uses the division algorithm to repeatedly find the remainder of a division until the remainder is zero. At this point, the divisor is the GCD of the original two numbers.

Euclidean Using subtraction

GCD (a, b)
1. if a==0:
2.   return b
3. while b != 0:
4.   if (a>b)
5.     a = a-b
6.   else
7.     b = b-a
8. return a

Time Complexity: O(n) where n = a+b

Euclidean Using division

GCD (a, b)
1. if b == 0:
2.   return a
3. else  
4.   return GCD (b, a mod b);

Time Complexity: O(log(n)) where n = a+b

Note: In the call, GCD (b, a mod b), larger number is set as b and divisor is set as a mod b which is less than b ( b > a%b >= 0).

Example

For example, let’s find the GCD of 54 and 24 using the Euclidean algorithm:
GCD(54, 24) = GCD(24, 6) = GCD(6, 0) = 6
As you can see, the algorithm first finds the remainder when 54 is divided by 24, which is 6. Then it finds the remainder when 24 is divided by 6, which is 0. At this point, the algorithm returns the divisor, which is 6, and this is the GCD of 54 and 24.

Code Implementation

//
//  main.cpp
//  GCD
//
//  Created by Himanshu on 19/09/21.
//

#include <iostream>
using namespace std;

int gcdUsingSubtarction (int a, int b) {

    if (a == 0) {
        return b;
    }

    while (b != 0) {
       if (a>b)
          a = a - b;
      else
         b = b - a;
     }

    return a;
}

int gcdUsingDivision (int a, int b) {

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

}

int main() {
    int a = 7, b = 43;
    
    printf("GCD of %d and %d using subtraction is %d \n", a, b, gcdUsingSubtarction(a, b));
    printf("GCD of %d and %d using division is %d \n", a, b, gcdUsingDivision(a, b));
 
    a = 21;
    b = 343;
    
    printf("GCD of %d and %d using subtraction is %d \n", a, b, gcdUsingSubtarction(a, b));
    printf("GCD of %d and %d using division is %d \n", a, b, gcdUsingDivision(a, b));
    
    return 0;
}

Output

GCD of 7 and 43 using subtraction is 1 
GCD of 7 and 43 using division is 1 
GCD of 21 and 343 using subtraction is 7 
GCD of 21 and 343 using division is 7 

Here’s a working example: Ideone

Practice problem

Shuttle Problem

Solution (You should try to solve this problem yourself first) – CodeChef