Eucledian GCD Algorithm
The Euclidean GCD Algorithm, or Euclidean Algorithm, is a highly efficient method for finding the greatest common divisor (GCD) of two integers. The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The algorithm is based on the principle that the GCD of two numbers remains the same when the smaller number is subtracted from the larger number. By repeatedly applying this principle, the algorithm eventually reaches a pair of numbers where the smaller number divides the larger number exactly, and this smaller number is the GCD.
The Euclidean GCD Algorithm can be implemented in two main ways: subtraction-based and division-based. In the subtraction-based method, the smaller number is repeatedly subtracted from the larger number until the two numbers become equal, which is the GCD. This process can be quite slow for large input numbers. The division-based method, on the other hand, is more efficient and widely used. In this approach, the algorithm starts with two input numbers and divides the larger number by the smaller number, taking the remainder as the new smaller number. This process is repeated until the remainder becomes zero. The divisor in the last step, which is the last non-zero remainder, is the GCD of the original two numbers. This algorithm is not only efficient for small numbers but also scales well for very large numbers, making it a popular choice in various applications, including cryptography and computer algebra systems.
function euclideanGCDRecursive (first, second) {
/*
Calculates GCD of two numbers using Euclidean Recursive Algorithm
:param first: First number
:param second: Second number
:return: GCD of the numbers
*/
if (second === 0) {
return first
} else {
return euclideanGCDRecursive(second, (first % second))
}
}
function euclideanGCDIterative (first, second) {
/*
Calculates GCD of two numbers using Euclidean Iterative Algorithm
:param first: First number
:param second: Second number
:return: GCD of the numbers
*/
while (second !== 0) {
const temp = second
second = first % second
first = temp
}
return first
}
function main () {
const first = 20
const second = 30
console.log('Recursive GCD for %d and %d is %d', first, second, euclideanGCDRecursive(first, second))
console.log('Iterative GCD for %d and %d is %d', first, second, euclideanGCDIterative(first, second))
}
main()
