How to use binary euclidean algorithm In Javascript
This approach utilizes the binary Euclidean algorithm, which is an optimized version of the Euclidean algorithm that uses bitwise operations. It efficiently computes the G.C.D of two numbers by halving the numbers until one of them becomes zero, providing a faster G.C.D computation through recursion.
Example: In the base cases, if one of the numbers is zero, the G.C.D is the other number. We recursively call the function until we find the base case, adjusting the numbers according to the binary Euclidean algorithm’s logic.
Javascript
function gcdRecursiveBinaryEuclidean(a, b) { // Base cases if (a === 0) { return b; } if (b === 0) { return a; } // If both numbers are even if ((a & 1) === 0 && (b & 1) === 0) { return gcdRecursiveBinaryEuclidean(a >> 1, b >> 1) << 1; } // If 'a' is even and 'b' is odd else if ((a & 1) === 0) { return gcdRecursiveBinaryEuclidean(a >> 1, b); } // If 'a' is odd and 'b' is even else if ((b & 1) === 0) { return gcdRecursiveBinaryEuclidean(a, b >> 1); } // If both numbers are odd and 'a' > 'b' else if (a >= b) { return gcdRecursiveBinaryEuclidean((a - b) >> 1, b); } // If both numbers are odd and 'a' < 'b' else { return gcdRecursiveBinaryEuclidean(a, (b - a) >> 1); } } // Example usage const num1 = 36; const num2 = 48; console.log( `G.C.D of ${num1} and ${num2} is: ${gcdRecursiveBinaryEuclidean(num1, num2)}`, ); |
G.C.D of 36 and 48 is: 12
JavaScript Program to Find G.C.D Using Recursion
The greatest common divisor (G.C.D) of two integers is the largest positive integer that divides both numbers without leaving a remainder. In JavaScript, finding the greatest common divisor (G.C.D) of two numbers using recursion is a common programming task. Recursion is a powerful technique where a function calls itself to solve smaller instances of the same problem until it reaches a base case.
Below are the approaches to finding the G.C.D using recursion in JavaScript:
Syntax:
function functionName(parameters) {
// Base case
if (condition) {
// Return value or perform action
} else {
// Recursive call
functionName(modifiedParameters);
// Additional computation (optional)
}
}
Contact Us