Euclid’s Algorithm when % and / operations are costly
Euclid’s algorithm is used to find GCD of two numbers.
There are mainly two versions of algorithm.
Version 1 (Using subtraction)
C++
// Recursive function to return gcd of a and b int gcd( int a, int b) { if (a == b) return a; return (a > b) ? gcd(a - b, b) : gcd(a, b - a); } |
C
// Recursive function to return gcd of a and b int gcd( int a, int b) { if (a == b) return a; return (a > b)? gcd(a-b, b): gcd(a, b-a); } |
Java
// Recursive function to return gcd of a and b static int gcd( int a, int b) { if (a == b) return a; return (a > b) ? gcd(a - b, b) : gcd(a, b - a); } // This code is contributed by subham348. |
Python3
# Recursive function to return gcd of a and b def gcd(a, b): if (a = = b): return a return gcd(a - b, b) if (a > b) else gcd(a, b - a) # This code is contributed by subham348. |
C#
// Recursive function to return gcd of a and b static int gcd( int a, int b) { if (a == b) return a; return (a > b) ? gcd(a - b, b) : gcd(a, b - a); } // This code is contributed by subham348. |
Javascript
// Recursive function to return gcd of a and b function gcd(a, b) { if (a === b) return a; return (a > b)? gcd(a-b, b): gcd(a, b-a); } // This code is contributed by subham348. |
Time Complexity: O(max(a, b))
Auxiliary Space: O(1)
Version 2 (Using modulo operator)
C++
// Function to return gcd of a and b static int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); } |
C
// Function to return gcd of a and b int gcd( int a, int b) { if (a == 0) return b; return gcd(b%a, a); } |
Java
// Function to return gcd of a and b static int gcd( int a, int b) { if (a == 0 ) return b; return gcd(b%a, a); } // This code is contributed by subham348. |
C#
// Function to return gcd of a and b static int gcd( int a, int b) { if (a == 0) return b; return gcd(b%a, a); } // This code is contributed by subham348. |
Javascript
// Function to return gcd of a and b function gcd(a, b) { if (a === 0) return b; return gcd(b%a, a); } // This code is contributed by subham348. |
Python3
# Python3 Function to return gcd of a and b def gcd(a, b): if (a = = 0 ): return b return gcd(b % a, a) # This code is contributed by phasing17 |
Time Complexity: O(log(max(a, b)))
Auxiliary Space: O(1)
Which of the above two is more efficient?
Version 1 can take linear time to find the GCD, consider the situation when one of the given numbers is much bigger than the other. Version 2 is obviously more efficient as there are less recursive calls and takes logarithmic time.
Consider a situation where modulo operator is not allowed, can we optimize version 1 to work faster?
Below are some important observations. The idea is to use bitwise operators. We can find x/2 using x>>1. We can check whether x is odd or even using x&1.
gcd(a, b) = 2*gcd(a/2, b/2) if both a and b are even.
gcd(a, b) = gcd(a/2, b) if a is even and b is odd.
gcd(a, b) = gcd(a, b/2) if a is odd and b is even.
Below is C++ implementation.
C++
// Efficient C++ program when % and / are not allowed int gcd( int a, int b) { // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ((a & 1) == 0 && (b & 1) == 0) return gcd(a >> 1, b >> 1) << 1; // If a is even and b is odd, divide a by 2 if ((a & 1) == 0 && (b & 1) != 0) return gcd(a >> 1, b); // If a is odd and b is even, divide b by 2 if ((a & 1) != 0 && (b & 1) == 0) return gcd(a, b >> 1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b) ? gcd(a - b, b) : gcd(a, b - a); } |
C
// Efficient C++ program when % and / are not allowed int gcd( int a, int b) { // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ( (a & 1) == 0 && (b & 1) == 0 ) return gcd(a>>1, b>>1) << 1; // If a is even and b is odd, divide a by 2 if ( (a & 1) == 0 && (b & 1) != 0 ) return gcd(a>>1, b); // If a is odd and b is even, divide b by 2 if ( (a & 1) != 0 && (b & 1) == 0 ) return gcd(a, b>>1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b)? gcd(a-b, b): gcd(a, b-a); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { static int gcd( int a, int b) { // Base cases if (b == 0 || a == b) return a; if (a == 0 ) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ((a & 1 ) == 0 && (b & 1 ) == 0 ) return gcd(a >> 1 , b >> 1 ) << 1 ; // If a is even and b is odd, divide a by 2 if ((a & 1 ) == 0 && (b & 1 ) != 0 ) return gcd(a >> 1 , b); // If a is odd and b is even, divide b by 2 if ((a & 1 ) != 0 && (b & 1 ) == 0 ) return gcd(a, b >> 1 ); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b) ? gcd(a - b, b) : gcd(a, b - a); } // Driver Code public static void main(String[] args) { System.out.println(gcd( 54 , 36 )); } } // This code is contributed by phasing17 |
Python3
def gcd(a, b): # Base cases if (b = = 0 or a = = b): return a if (a = = 0 ): return b # If both a and b are even, divide both a and b by 2. # And multiply the result with 2 if ((a & 1 ) = = 0 and (b & 1 ) = = 0 ): return gcd(a >> 1 , b >> 1 ) * 2 # If a is even and b is odd, divide a by 2 if ((a & 1 ) = = 0 and (b & 1 ) ! = 0 ): return gcd(a >> 1 , b) # If a is odd and b is even, divide b by 2 if ((a & 1 ) ! = 0 and (b & 1 ) = = 0 ): return gcd(a, b >> 1 ) # If both are odd, then apply normal subtraction algorithm. # Note that odd-odd case always converts odd-even case after one recursion return gcd(a - b, b) if a > b else gcd(a, b - a) # This code is contributed by Vikram_Shirsat |
C#
// C# program to implement // the above approach using System; class GFG { // Efficient C++ program when % and / are not allowed int gcd( int a, int b) { // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ( (a & 1) == 0 && (b & 1) == 0 ) return gcd(a>>1, b>>1) << 1; // If a is even and b is odd, divide a by 2 if ( (a & 1) == 0 && (b & 1) != 0 ) return gcd(a>>1, b); // If a is odd and b is even, divide b by 2 if ( (a & 1) != 0 && (b & 1) == 0 ) return gcd(a, b>>1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b)? gcd(a-b, b): gcd(a, b-a); } } // This code is contributed by code_hunt. |
Javascript
// Efficient JavaScript program when % and / are not allowed function gcd(a, b) { // Base cases if (b == 0 || a == b) return a; if (a == 0) return b; // If both a and b are even, divide both a // and b by 2. And multiply the result with 2 if ( (a & 1) == 0 && (b & 1) == 0 ) return gcd(a>>1, b>>1) << 1; // If a is even and b is odd, divide a by 2 if ( (a & 1) == 0 && (b & 1) != 0 ) return gcd(a>>1, b); // If a is odd and b is even, divide b by 2 if ( (a & 1) != 0 && (b & 1) == 0 ) return gcd(a, b>>1); // If both are odd, then apply normal subtraction // algorithm. Note that odd-odd case always // converts odd-even case after one recursion return (a > b)? gcd(a-b, b): gcd(a, b-a); } // This code is contributed by phasing17 |
Time Complexity: O(log(max(a, b)))
Auxiliary Space: O(1)
This article is compiled by Shivam Agrawal.
Contact Us