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

# Developed for CSci 556, Multiparadigm Programming, Spring 2015

# 34567890123456789012345678901234567890123456789012345678901234567890

# 2015-02-08: Developed from 2013 Lua version

defmodule GCD do

  @moduledoc """  
  This greatest common divisor (gcd) module is adapted from a Lua
  version, wich itself was adapted from the Scheme code from section
  1.2.5 of Abelson and Sussman's Structure and Interpretation of
  Computer Programs (SICP) textbook.
  """

  @doc """
  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
  """

  def gcd(a,0) do a end
  
  def gcd(a,b) when is_integer(a) and is_integer(b) do
    gcd(b, rem(a,b))   # tail recursion
  end

end