Iterative Stein's (binary) GCD (greatest common divisor) algorithm in Nim

gcd.nim

proc gcd(a, b: int): int =
  var (a, b) = (a, b)
  if a == 0: return b
  if b == 0: return a

  var k = 0
  while ((a or b) and 1) == 0:
    a = a shr 1
    b = b shr 1
    k += 1

  while (a and 1) == 0: a = a shr 1

  while b != 0:
    while (b and 1) == 0: b = b shr 1
    if a > b: swap a,b
    b -= a

  result = a shl k