--[[ Functional Programming Example -- Greatest Common Divisor
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 658, Software Language Engineering, Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-09-08: Completed prototype

This greatest common divisor (gcd) function is adapted from section
1.2.5 of Abelson and Sussman's Structure and Interpretation of
Computer Programs (SICP) textbook.

--]]


-- Function "gcd" computes the greatest common divisor of its two
-- nonegative number arguments using Euclid's algorithm. It is based
-- on property: If r is the remainder of a divided by b, then the
-- common divisors of a and b are precisely the same as the common
-- divisors of b and r.  
-- Time complexity:  O(log max(a,b))
-- Space complexity: O(1) with tail call optimization

local function gcd(a,b)
  if type(a) == "number" and type(b) == "number" and 
        a == math.floor(a) and b == math.floor(b) then
    if b == 0 then
      return a
    else
      return gcd(b, a % b) -- tail recursion
    end
  else
    error("Invalid argument to gcd (" .. tostring(a) .. "," .. 
          tostring(b) .. ")", 2)
  end
end


-- Testing of gcd

local one = {60,61,62,63,64,65,66,67,68,69}
local two = {160,161,162,163,164,165,166,167,168,169}

print("\nGreatest Common Divisor")
for _, x in ipairs(one) do
  for _, y in ipairs(two) do
    print("GCD of " .. tostring(x) .. " and " .. tostring(y) .. 
          " is " ..tostring(gcd(x,y)))
  end
end

one = {64}
two = {-160,-161,-162,-163,-164,-165,-166,-167,-168,-169}

print("\nGreatest Common Divisor")
for _, x in ipairs(one) do
  for _, y in ipairs(two) do
    print("GCD of " .. tostring(x) .. " and " .. tostring(y) .. 
          " is " ..tostring(gcd(x,y)))
  end
end

print("\nForced error: Call with nonintegral argument.")
local a, b = 2.5, 5
print("gcd(" .. tostring(a) .. "," .. tostring(b) .. ") = " .. 
      tostring(gcd(a,b)))