Greatest common divisor (Euclid)

Write gcd(a, b) -> int: the greatest common divisor of two integers, using Euclid's algorithm. Don't use math.gcd (the tests check).

• -10^18 <= a, b <= 10^18. The result is never negative, and by convention gcd(0, 0) = 0 and gcd(x, 0) = |x|.

gcd(12, 18)     # 6
gcd(17, 5)      # 1
gcd(0, 9)       # 9
gcd(-12, 18)    # 6
gcd(0, 0)       # 0

Euclid: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = |a|. The larger number at least halves every two steps, so it takes O(log) steps. Subtracting the smaller from the larger one step at a time is far too slow when one number is huge and the other is small; trying every candidate divisor is worse.