Euclid's Algorithm - JavaScript

Question

I'm new to JavaScript and I'm learning about recursive functions. Specifically, I'm working on Euclid's algorithm. It all makes sense to me except for the base case on line 2 "if ( ! b) { return a; }. I understand that at some point a % b will be equal to NaN and this is when the recursive call should stop. But what does "if ( ! b)" mean in it's simplest form? I can't wrap my head around this. I appreciate the feedback in advance!

// Euclid's Algorithm 

var gcd = function(a, b) {  
   if (!b) {  
       return a;  
   }  

   return gcd(b, a % b);  
};  
console.log(gcd(462, 910));

You can find some info about that here: http://www.codeproject.com/Articles/182416/A-Collection-of-JavaScript-Gotchas#nullundefined — higuaro, Aug 17 '15 at 03:15
And after that article, you can find lot of info here http://stackoverflow.com/questions/19839952/all-falsey-values-in-javascript — higuaro, Aug 17 '15 at 03:18

score 2 · Answer 1 · answered Aug 17 '15 at 03:16

This is the rationale behind Euclid's algorithm.

gcd(a, b) = gcd(b, a%b)

But except when b is 0. What is the result in this case? You can imagine that 0 has actually infinite factors in it: you can divide 0 by anything and the remainder will always be 0.

From this, we can derive that

gcd(a, 0) = a

And that's the stop case of the algorithm. if (!b) is actually checking if b===0, and returning a in this case.

Nimix · Answer 2 · 2015-08-17T03:27:03.753

2

(! b) is evaluating the variable b to return the value of false. In JavaScript NaN is falsey which means it's not false, but it will evaluate to false in a Boolean evaluation.

As others have mentioned, the variable b will equal 0 and not NaN. I was just explaining how NaN evaluates for the sake of the original question.

edited Aug 17 '15 at 03:27

answered Aug 17 '15 at 03:18

Nimix

61
3

Actually, Nimix, while both your sentences are true, the second is irrelevant, since `b` never actually becomes `NaN` - it stops one step short of that when it reaches zero. – paxdiablo Aug 17 '15 at 03:24

score 2 · Answer 3 · answered Oct 20 '18 at 22:05

The base case for the Euclidean Algorithm happens when one of the parameters are equal to zero, which means the greatest common divisor of both numbers is the non-zero number. you can refer to this link to see some examples: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

This is how I implemented the Euclidean Algorithm:

   function gcd(a, b) {
        // base cases
        if(a === 0) { return b;}
        if(b === 0) { return a;}

        // decrease and conqure - recursion
        return gcd(b, a % b);
    }

    console.log(gcd(9, 6));
    console.log(gcd(6, 9));

score 0 · Answer 4 · answered Aug 17 '15 at 03:17

Put very simply, in this case, !b is the same as b == 0. Zero as a truthy value is false so !0 will be true.

In other words, the function returns a when b is zero, otherwise it carries on through more recursive levels.

Your contention that a % b will become NaN is actually false - the fact that b becomes zero, and that you detect that, means you never actually divide anything by zero to get NaN.

score 0 · Answer 5 · edited May 03 '21 at 20:36

0

//I'm glad that I can help others, here is my version:
//Euclid's algorithm:
//1)Find reminder of division m by n
//2)If remainder is zero, n is a solution
//3)Reduce(if r != zero)
const euclid = function(num1, num2){
    //compute the remainder:
    var remainder = num1 % num2;
    if(remainder == 0){
        return num2;
   
    }else{
        //step 3:
        num1 = num2;
        num2 = remainder;
       return euclid(num1, num2);
    }
}
//test the result:

console.log(euclid(80, 30));

edited May 03 '21 at 20:36

Scott Sauyet

49,207
4
49
103

answered May 03 '21 at 06:33

YouKnowWho

1

Welcome to StackOverflow! Thank you for your answer. To make the answer better, please add some explanation about why you think this might be an improvement on other answers here. Also what happens (and what do you think should happen) if `num2` is zero? – Scott Sauyet May 03 '21 at 20:39

Euclid's Algorithm - JavaScript

5 Answers5