Javascript Practice 69: JS Hero - gcd

 

Question: 

Write a function gcd that takes two natural numbers and calculates their gcd.

Example: gcd (6, 15) should return 3.

Answer: 

function gcd (a,b) {

if (b == 0) {

return a;

} else { 

let remainder = a % b; 

return gcd (b, remainder);

}

}

--- we need to understand 'euclid's alogrithm for gcd'

--- if we subtract a smaller number from a larger (we reduce a larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.

--- now instead of subtraction, if we divide the smaller number, the algorithm stops when we find remainder 0.

--- If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop

--- If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.

> we declare a function 'gcd'

> it has 2 parameters: 'a' and 'b'

> if b is equal to 0, then a shall be the gcd (if you understand euclids alogorithm)

> if b is not equal to 0, then we calculate the remainder

> we create a variable 'remainder'

> we initialize it with a value / remainder that we get by dividing a by b; using modulo operator

> like this a % b; we use the modulo / remainder operator

> we then return the same function gcd with two parameters (b, remainder) 

> this will again call the function gcd (a,b) but this time it will have a value of (a = b, b = remainder)

>>> we should try and understand this with an example to get clarity

>>> let us assume that we call the function gcd with some numbers

>>> like this: gcd (45, 99) ====>>> gcd (a,b)

>>> first it will check if b = 0; but b = 99

>>> so it will execute the code in the else block

>>> it will divide 45 / 99 using the remainder operator and store the output in the remainder variable

>>> the output shall be 45 % 99 = 45; so remainder = 45

>>> now we return the gcd function again with new values

>>> gcd (99, 45) ====>>> gcd (b = 99, remainder as calculated = 45)

>>> so our original parameters shall now be gcd(99, 45) ====>>> gcd(a = 99, b = 45)

>>> first it will check if b = 0; but b = 45

>>> so it will execute the code in the else block

>>> it will divide 99 / 45 using the remainder operator and store the output in the remainder variable

>>> the output shall be 99 % 45 = 9; so new remainder = 9

>>> now we return the gcd function again with new values

>>> gcd (45, 9) ====>>> gcd (b = 45, remainder as calculated = 9)

>>> so our original parameters shall now be gcd(45, 9) ====>>> gcd(a = 45, b = 9)

>>> again it will check if b = 0; but b = 9 >>> so it will execute the code in the else block

>>> it will divide 45 / 9 using the remainder operator and store the output in the remainder variable

>>> the output shall be 45 % 9 = 0; so remainder = 0

>>> now we return the gcd function again with new values

>>> gcd (9, 0) ====>>> gcd (b = 9, remainder as calculated = 0)

>>> so our original parameters shall now be gcd(9, 0) ====>>> gcd(a = 9, b = 0)

>>> again it will check if b = 0; and this time b = 0 

>>> so it will return a which is 9 

>>> and this is our GCD value for 2 numbers