Euclid's greatest common divisor and least common multiple

The GCD of two numbers is the biggest number that divides both. I was going through some books and found Euclid's formula, which I am fairly certain is one of those formulas I learned in the past and just forgotten.

Anyway, the book was mentioning it has complexity O(logN) where N is the sum of the two numbers:

gcd(a, b){

  if(b == 0 ) return a;

  return gcd(b, a % b);

}

However, this assumes the modulo operation is done in constant time regardless of the input numbers, a  more realistic complexity is somewhere O(N logN) as the modulo might need to be computed in linear time.

A better approach uses bit operations instead and gives a O((logN)^2) time since the operations it uses can be computed in O(logN) time:

gcd(a, b){

  return gcd(a, b, 1);

}

gcd(a, b, res){

  if(a == b) return res * a;

  if(a % 2 == 0 && b % 2 == 0) return gcd(a >> 1, b >> 1, res << 1);

  if(a % 2 == 0) return gcd(a >> 1, b , res);

  if(b % 2 == 0) return gcd(a, b >> 1, res);

  if(a > b) return gcd(a - b, b, res);

  return gcd(a, b - a, res);

}

As an added bonus, we can use this to compute the LCM which is the smallest number divisible by both:

lcm(a,b){

return a * b / gcd(a, b);

}

You can find gcd and lcm on my Gist.