JavaScript: Calculate the extended Euclid Algorithm or extended GCD
JavaScript Math: Exercise-47 with Solution
Write a JavaScript function to calculate the extended Euclid Algorithm or extended GCD.
In mathematics, the Euclidean algorithm[a], or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in Euclid's Elements. It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.
Visual Presentation:
Sample Solution:
JavaScript Code:
// Define a function named Euclid_gcd that calculates the greatest common divisor (GCD) using Euclid's algorithm.
function Euclid_gcd(a, b) {
// Convert 'a' and 'b' to numbers.
a = +a;
b = +b;
// Check if 'a' or 'b' is NaN (Not a Number).
if (a !== a || b !== b) {
return [NaN, NaN, NaN];
}
// Check if 'a' or 'b' is Infinity or -Infinity.
if (a === Infinity || a === -Infinity || b === Infinity || b === -Infinity) {
return [Infinity, Infinity, Infinity];
}
// Check if 'a' or 'b' are decimals.
if ((a % 1 !== 0) || (b % 1 !== 0)) {
return false;
}
// Initialize variables for signs and quotient.
var signX = (a < 0) ? -1 : 1,
signY = (b < 0) ? -1 : 1,
x = 0,
y = 1,
u = 1,
v = 0,
q, r, m, n;
// Get the absolute values of 'a' and 'b'.
a = Math.abs(a);
b = Math.abs(b);
// Implement Euclid's algorithm to find the GCD.
while (a !== 0) {
q = Math.floor(b / a);
r = b % a;
m = x - u * q;
n = y - v * q;
b = a;
a = r;
x = u;
y = v;
u = m;
v = n;
}
// Return an array containing the GCD, and the coefficients for 'a' and 'b'.
return [b, signX * x, signY * y];
}
// Output the result of Euclid's algorithm for GCD calculation with inputs 17 and 4.
console.log(Euclid_gcd(17, 4));
Output:
[1,1,-4]
Flowchart:
Live Demo:
See the Pen javascript-math-exercise-47 by w3resource (@w3resource) on CodePen.
Improve this sample solution and post your code through Disqus.
Previous: Write a JavaScript function to calculate the divisor and modulus of two integers.
Next: Write a JavaScript function to calculate the falling factorial of a number.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://www.w3resource.com/javascript-exercises/javascript-math-exercise-47.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics