Feb  8 22:24 2015 exponentiation.ex Page 1


# Functional Programming Example #  Exponentiation
# H. Conrad Cunningham, Professor
# Computer and Information Science
# University of Mississippi

# Developed for CSci 556, Multiparadigm Programming, Spring 2015

# 34567890123456789012345678901234567890123456789012345678901234567890

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

# This exponentiation module is adapted from a Lua version, which
# itself is adapted from the Scheme code in section 1.2.4 of Abelson
# and Sussman's Structure and Interpretation of Computer Programs
# (SICP)

defmodule Expt do

  # Function "expt1" 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

  def expt1(b,n) when is_number(b) and is_integer(n) and n >= 0 do 
    _expt1(b,n)
  end
  
  # private auxiliary to avoid repeated type checks
  defp _expt1(_,0) do 1 end
  defp _expt1(b,n) do b * _expt1(b,n-1) end


  # Function "expt2" computes b^n using tail recursion.

  # Time complexity:  O(n) recursive calls
  # Space complexity: O(1) with tail call optimization

  def expt2(b,n) when is_number(b) and is_integer(n) and n >= 0 do 
    _expt2(b,n,1)
  end

  # private tail recursive auxiliary (called expt_inter in SICP)
  defp _expt2(_,0,p) do p end
  defp _expt2(b,n,p) do _expt2(b,n-1,b*p) 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








Feb  8 22:24 2015 exponentiation.ex Page 2


  # Time complexity:  O(log n) recursive calls
  # Space complexity: O(log n) active recursive calls needing
	#                   stack frames

  def expt3(b,n) when is_number(b) and is_integer(n) and n >= 0 do
     _expt3(b,n)
  end

  defp _expt3(_,0) do 1 end

  defp _expt3(b,n) do
    if rem(n,2) == 0  do  #  i.e. even
      exp = _expt3(b,div(n,2))
      exp * exp           #  backward recursion
    else                  # i.e. odd
      b * _expt3(b,n-1)   #  backward recursion
    end
  end

end