Understanding the Euclidean Algorithm for Finding the Greatest Common Divisor (GCD) C++ Implementation

Published in

ProgrammerCave

6 min readAug 5, 2023

Introduction

The Euclidean algorithm has stood the test of time as one of the most efficient methods for finding the Greatest Common Divisor (GCD) of two integers. Its elegant simplicity and effectiveness have made it a staple in various mathematical and computational applications. In this comprehensive guide, we will delve into the inner workings of the Euclidean algorithm, step-by-step, and explore its recursive and iterative implementations. By the end of this article, you will have a deep understanding of the Euclidean algorithm, allowing you to apply it confidently in your mathematical endeavors.

Algorithm

The algorithm is based on the principle that the GCD of two numbers remains the same if the larger number is replaced by its remainder when divided by the smaller number. Here’s how the Euclidean algorithm works step-by-step, along with examples:

Step 1: Take Two Integers

The first step in the Euclidean algorithm involves choosing two integers, a and b, for which we want to find the GCD. It is crucial to ensure that a is greater than or equal to b. In the rare case that a is smaller than b, a simple swap of the two numbers will suffice to maintain consistency throughout the process.

Example: For this demonstration, let’s take a = 48 and b = 18.

Step 2: Divide and Find Remainder

With our chosen integers, we proceed to divide a by b and find the remainder, which we denote as r. The equation is as follows:

a ÷ b = q with a remainder of r

where q represents the quotient. The remainder r is what we will focus on in the subsequent steps.

Example: For our example, 48 ÷ 18 = 2 with a remainder of 12. Hence, r = 12.

Step 3: Is Remainder Zero?

The crux of the Euclidean algorithm lies in this pivotal step. We need to determine if the remainder r is zero. If r is indeed zero, then we have found the GCD of the original numbers ( a and b), and our journey is complete. However, if r is not zero, we must continue to the next step.

Example: As our r = 12, which is not zero, we must continue with the algorithm.

Step 4: Update Values

In this step, we update the values of a and b. We set a to the previous value of b, and b to the previous value of r. This crucial update allows us to replace the larger number a with its remainder r when divided by the smaller number b.

Example: After this update, a = 18 (previous value of b) and b = 12 (previous value of r).

Step 5: Repeat the Process

The beauty of the Euclidean algorithm lies in its simplicity and repetitiveness. We now repeat steps 2 to 4 until the remainder r becomes zero. The GCD will be the last non-zero remainder found during this process.

Example:

18 ÷ 12 = 1 with a remainder of 6 (new value of r).
12 ÷ 6 = 2 with a remainder of 0 (the new value of r).
Since r = 0, we stop. The last non-zero remainder is 6.

Step 6: Final Result

The culmination of our journey arrives at this step. The GCD of the original numbers a and b is simply the last non-zero remainder found in the process.

Example: In our case, the GCD of 48 and 18 is 6.

Recursive Implementation of Euclidean Algorithm

As promised, we shall now explore the recursive implementation of the Euclidean algorithm. Recursion adds an element of elegance to the already efficient algorithm, making it a delightful mathematical concept.

The recursive approach to finding the GCD involves defining a function that calls itself with updated arguments until the base case is reached. The base case, as you might recall, is when the remainder becomes zero, and we return the current value of b, which is the GCD.

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

Iterative Implementation of Euclidean Algorithm

Now, let us venture into the iterative version of the Euclidean algorithm. While the recursive implementation showcases the beauty of recursion, the iterative version emphasizes the algorithm’s efficiency.

In the iterative approach, we employ a while loop to repeatedly perform the necessary steps until the remainder becomes zero. The loop allows us to update the values of a and b efficiently, eliminating the need for recursive function calls.


int iterative_gcd(int a, int b) {
    int temp;
    while (b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

In both the recursive and iterative implementations, the functions recursive_gcd and iterative_gcd take two integer arguments a and b, and they return the GCD of those two numbers. The choice between these implementations depends on the specific use case and programming preferences.

If you’re interested in exploring the C++ implementation, you can find the complete code on our Github repository.

Conclusion

The Euclidean algorithm’s beauty lies in its versatility and efficiency, making it a valuable tool in diverse mathematical and computational scenarios. Whether you are calculating GCDs for advanced number theory or simply implementing it in a programming project, the Euclidean algorithm will serve you exceptionally well.

What is the Euclidean algorithm used for? The Euclidean algorithm is primarily used to find the Greatest Common Divisor (GCD) of two integers. It has applications in various mathematical fields, including number theory and cryptography.
Is the Euclidean algorithm always efficient? Yes, the Euclidean algorithm is known for its efficiency in finding the GCD of two numbers. Its time complexity is proportional to the number of digits in the smaller input number.
Can the Euclidean algorithm handle negative integers? Yes, the Euclidean algorithm can handle negative integers. The absolute values of the numbers are used in the calculations, so the sign does not affect the final result.
Are there alternative methods for finding the GCD? Yes, there are other methods for finding the GCD, such as the prime factorization method and the binary GCD algorithm. However, the Euclidean algorithm is widely preferred due to its simplicity and efficiency.
Can the Euclidean algorithm find the GCD of more than two numbers? The Euclidean algorithm is designed to find the GCD of two numbers. To find the GCD of multiple numbers, it can be applied iteratively or recursively to a pair of numbers at a time.

Originally published at https://programmercave.com on August 5, 2023.

This blog is sponsored by:

CodeDesign. ai: Experience the power of AI website building with CodeDesign. ai! Build and deploy your stunning website in minutes, no coding is required. With its intuitive interface and advanced AI technology, you’ll have a professional website up and running in no time. Don’t miss out on this game-changing platform!

Scaler Academy: If you are considering enrolling in Scaler Academy and would like a referral and discount on your fees, I can help. As a Scaler alumnus, I can provide referrals. Use my referral link if you have decided to join Scaler Academy. If you want to know more about Scaler Academy, drop a mail at programmercave@gmail.com

TopCoder: Looking for short-term gigs to boost your income? Look no further! Join TopCoder’s Gig platform today! As a talented programmer or freelancer, you have the skills that are in high demand. With TopCoder’s Gig, you can find exciting opportunities to work on short projects and earn extra income on the side.

Geektrust: Are you passionate about development and want to find a job that utilizes your skills? Check out Geektrust for resources and opportunities in the field of development.

KuCoin: Discover the next crypto gem on KuCoin! Join the global community of crypto holders and unlock a world of investment opportunities. With 1 out of 4 crypto holders worldwide choosing KuCoin, you’re in good company. Sign up now with my referral link and start your crypto journey. Don’t miss out on the chance to be part of the future of finance. Join KuCoin today!

Best Laptop for Programming (2023)

Here: Best Laptop for Programming (2023)

Also, don’t miss out on Best Sellers in Computers & Accessories