--[[ Functional Programming Example -- Exponentiation
     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

These factorial functions are adapted from section 1.2.4 of Abelson
and Sussman's Structure and Interpretation of Computer Programs (SICP)
textbook.

--]]

-- Function "expt" computes b^n (b raised to power n) using backward
-- linear recursion.
-- Time complexity:  O(n) recursive calls
-- Space complexity: O(n) active recursive calls

local function expt(b,n) 
  if type(b) == "number" and type(n) == "number" and n >= 0 and 
      n == math.floor(n) then
    if n == 0 then
      return 1
    else  -- n > 0
      return b * expt(b,n-1)  -- backward recursion
    end
  else
    error("Invalid arguments to expt: " .. 
          tostring(b) .. "^" .. tostring(n))
  end
end

-- Function "expt2" computes b^n using tail recursion.
-- Time complexity:  O(n) recursive calls
-- Space complexity: O(1) with tail call optimization

local function expt2(b,n)

  local function expt_iter(m,p) -- b known from outer scope
    if m == 0 then              --   p is accumulator
      return p
    else  -- m > 0
      return expt_iter(m-1,b*p) -- tail recursion
    end
  end

  if type(b) == "number" and type(n) == "number" and n >= 0 and 
      n == math.floor(n) then
    return expt_iter(n,1)
  else
    error("Invalid arguments to expt: " .. 
          tostring(b) .. "^" .. tostring(n))
  end
end


-- Fuction "expt3" computes b^n using a logarithmic algorithm and
-- backward recursion.  It takes advantage of squaring.
--
--     b^n = (b^(n/2)) * (b^(n/2)) if n even
--     b^n = b * b^(n-1)           if n odd
-- Time complexity:  O(log n) recursive calls
-- Space complexity: O(log n) active recursive calls needing stack frames

local function expt3(b,n)
  if type(b) == "number" and type(n) == "number" and n >= 0 and 
      n == math.floor(n) then
    if n == 0 then
      return 1
    elseif n % 2 == 0 then -- i.e. even
      local exp = expt3(b,n/2)
      return exp * exp        -- backward recursion
    else -- i.e. odd
      return b * expt3(b,n-1) -- backward recursion
    end
  else
    error("Invalid arguments to expt: " .. 
          tostring(b) .. "^" .. tostring(n))
  end
end


-- Testing of expt

local bases = {2,3,6}
local powers = {0,1,2,3,4,5,6,7,8,9,10,20}

print("\nBackward linear recursive exponentiation algorithm")
for _, b in ipairs(bases) do
  for _, n in ipairs(powers) do
    local exp = expt(b,n)
    print(tostring(b) .. "^" .. tostring(n)  .. " = " .. 
          tostring(exp))
  end
end 

-- Testing of expt2

print("\nTail recursive exponentiation algorithm")
for _, b in ipairs(bases) do
  for _, n in ipairs(powers) do
    local exp = expt2(b,n)
    print(tostring(b) .. "^" .. tostring(n)  .. " = " ..
          tostring(exp))
  end
end 


-- Testing of expt3

print("\nLogarithmic exponentiation algorithm")
for _, b in ipairs(bases) do
  for _, n in ipairs(powers) do
    local exp = expt3(b,n)
    print(tostring(b) .. "^" .. tostring(n)  .. " = " .. 
          tostring(exp))
  end
end 

print("\nForced error: Call with nonintegral argument.")
local b, n = 3, 2.5
local exp = expt3(b,n)
print(tostring(b) .. "^" .. tostring(n)  .. " = " ..
      tostring(exp))