gcd.rb

#!/usr/bin/env ruby

def gcd_rec(x, y)
  y == 0 ? x : gcd_rec(y, x%y)
end

def gcd_iter(x, y)
  x, y = y, x%y while y != 0
  x
end

# ax + by = gcd(x, y)
def xgcd_rec(x, y)
  if y == 0
    [x, 1, 0]
  else
    gcd, a, b = xgcd_rec(y, x%y)
    [gcd, b, a-x/y*b]
  end
end

# ax + by = gcd(x, y)
def xgcd_iter(x, y)
  a, next_a = 1, 0
  b, next_b = 0, 1
  while y != 0
    a, next_a = next_a, a-x/y*next_a
    b, next_b = next_b, b-x/y*next_b
    x, y  = y, x%y
  end
  [x, a, b]
end

# test
10.times do
  x = Random.rand(100) + 1
  y = Random.rand(100) + 1
  gcd_res = x.gcd(y)
  gcd_rec_res = gcd_rec(x, y)
  gcd_iter_res = gcd_iter(x, y)
  g1, a1, b1 = xgcd_rec(x, y)
  g2, a2, b2 = xgcd_iter(x, y)
  puts "#{gcd_res}\t#{gcd_rec_res}\t#{gcd_iter_res}\t#{a1}*#{x}+#{b1}*#{y}=#{g1}\t#{a2}*#{x}+#{b2}*#{y}=#{g2}"
end