Gcd Algorithm with JavaScript

12,000 2
Summary

The Euclidean algorithm provides an efficient method for calculating the greatest common divisor (GCD) of two integers. This technique is based on the principle that gcd(a,b) is equivalent to gcd(b, a mod b), with the base case defined as gcd(a,0) = a. The algorithm iteratively applies the modulo operation, reducing the numbers until a remainder of zero is achieved, at which point the non-zero number is the GCD. A straightforward JavaScript function demonstrates this recursive implementation, directly translating the mathematical definition into code.

How to find the greatest common divisor between two integers? We may encounter this problem frequently in interviews or other occasions.

An efficient metho to find gcd is the Euclidean algorithm, which uses the division algorithm in combination with the observation that the gcd of two numbers also divides their difference: divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd. Formally, it could be written as

gcd(a,0) = a

gcd(a,b) = gcd(b,a mod b)

 The code can be shown below;

function gcd(a,b){

            if(b==0){

                        return a;

            }else{

                        return gcd(b,a%b);

            }

}

 

JAVASCRIPT ALGORITHM GCD IMPLEMENTATION

  RELATED

  COMMENTS

2
Someone2841
Dec 6, 2012 at 3:52 pm
Reply
This function is recursive.. would not looping be better? For example: function gcd(a,b){ if(a%1!=0||b%1!=0) return -1; //Return -1 if a or b are not integers while(b!=0){var c = a%b; a=b; b=c;} //The algorithm return a; }
Someone2841
Dec 6, 2012 at 3:54 pm
Reply
/*Code with \\ representing line breaks:*/ \\ function gcd(a,b){ \\ if(a%1!=0||b%1!=0) return -1; //Return -1 if a or b are not integers \\ while(b!=0){var c = a%b; a=b; b=c;} //The algorithm \\ return a; \\ }