Key Takeaways: The Euclidean Algorithm is an ancient and incredibly efficient algorithm used to find the Greatest Common Divisor (GCD) of two numbers. It dramatically reduces the time complexity compared to brute-force searching.
As you advance in your Data Structures and Algorithms (DSA) journey, you will encounter problems that rely heavily on Number Theory and mathematical optimizations.
One of the oldest, most famous, and most practically useful algorithms in all of computer science is the Euclidean Algorithm, first described by the Greek mathematician Euclid in 300 BC.
In this comprehensive tutorial, we will explore exactly how the Euclidean Algorithm works, why it is so much faster than traditional math methods, and how you can implement it efficiently in your code.
Before we can dive into the algorithm itself, we need to quickly review what the Greatest Common Divisor (GCD)—sometimes called the Highest Common Factor (HCF)—actually is.
The GCD of two integers is the largest positive integer that divides both numbers evenly, leaving no remainder.
Example: What is the GCD of 12 and 8?
1, 2, 3, 4, 6, 121, 2, 4, 81, 2, 44If you were to program this using brute force, you would start at the smaller number (8) and loop downwards, checking every single number to see if it divides evenly into both.
While this works for 12 and 8, imagine trying to find the GCD of 10,458,921 and 8,912,450. A brute-force loop would take millions of operations. We need a faster way!
Euclid made a brilliant mathematical observation: The GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number.
For example, GCD(252, 105) is exactly the same as GCD(252 - 105, 105), which is GCD(147, 105).
While subtracting works, it can still be slow if one number is massively larger than the other. To speed this up, modern computer science replaces subtraction with Modulo Division (Finding the Remainder).
The algorithm follows a simple, repeating two-step rule:
a) by the smaller number (b), and find the remainder (r).a with b, and replace b with the remainder r.r becomes 0.0, the other number is your GCD!The Euclidean Algorithm in action. Type your own numbers into a and b above and click calculate to watch the steps happen dynamically!
Let's manually trace the algorithm to find the GCD of 48 and 18.
Initial State:
a = 48b = 18Step 1:
a / b (48 % 18).a becomes 18, and b becomes the remainder 12.Step 2:
a / b (18 % 12).a becomes 12, and b becomes the remainder 6.Step 3:
a / b (12 % 6).a becomes 6, and b becomes 0.Result:
Because b has reached 0, the algorithm stops. The final answer is the value left in a, which is 6. The Greatest Common Divisor of 48 and 18 is 6!
Because the Euclidean algorithm requires us to perform the exact same action repeatedly until a base condition (b == 0) is met, it is the absolute perfect candidate for Recursion.
However, it can also easily be written iteratively using a standard while loop. Let's look at both!
# Approach 1: Recursive Implementation (Elegant and Short) def gcd_recursive(a, b): # Base Case: When the remainder (b) hits 0, return a if b == 0: return a # Recursive Case: Call function with (b, a % b) return gcd_recursive(b, a % b)# Approach 2: Iterative Implementation (Saves memory) def gcd_iterative(a, b): while b != 0: # Store b temporarily temp = b # Update b to be the remainder b = a % b # Update a to be the old b a = temp return a
num1 = 48 num2 = 18
print(f"Recursive GCD of {num1} and {num2} is: {gcd_recursive(num1, num2)}") print(f"Iterative GCD of {num1} and {num2} is: {gcd_iterative(num1, num2)}")
The logic translates perfectly into modern JavaScript.
// Modern ES6 Arrow Function for Recursive GCD const gcdRecursive = (a, b) => { return b === 0 ? a : gcdRecursive(b, a % b); };// Standard Iterative Function function gcdIterative(a, b) { while (b !== 0) { let remainder = a % b; a = b; b = remainder; } return Math.abs(a); // Good practice to handle negative inputs }
console.log("GCD of 270 and 192 is:", gcdRecursive(270, 192));
Why is the Euclidean Algorithm considered one of the best algorithms in computer science? Because of its staggering mathematical efficiency.
O(log(min(a, b))). With every single step (modulo operation), the numbers shrink by at least half. This means even for incredibly massive 100-digit numbers, the algorithm will find the GCD in mere fractions of a millisecond!O(1). The iterative version uses a constant amount of memory because it just updates a few variables.O(log(min(a, b))). The recursive version requires extra memory for the Call Stack to handle the recursive function calls.The Euclidean algorithm isn't just an academic exercise. It powers the secure, encrypted web we use every day!
RSA (Rivest–Shamir–Adleman) is the public-key encryption system that secures credit card transactions and confidential communications across the internet. RSA relies on generating massive prime numbers. The Extended Euclidean Algorithm (an advanced version of this algorithm) is fundamentally required to generate the cryptographic keys!
Any application that renders mathematics or fractional dimensions needs to reduce fractions.
If you have the fraction 105 / 252, how do you simplify it?
GCD(105, 252), which is 21.21.5 / 12.If you need to find the LCM of two numbers, it is mathematically trivial once you have the GCD. The formula is simply:
LCM(a, b) = (a * b) / GCD(a, b)
What is the base case (stopping condition) for the recursive Euclidean Algorithm?
What is the Time Complexity of the Euclidean Algorithm?