module Expt
    (expt, expt2, expt3)
where

{-  Exponentiation Examples
    H. Conrad Cunningham, Professor
    Computer and Information Science
    University of Mississippi

Developed in Haskell for CSci 450/503 during Fall 204; based on Lua
code developed for CSci 658 during Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-09-08: Completed prototype in Lua
2014-09-18: Completed ptototype in Haskell

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
    Termination: Argument decreases by 1 toward 0 in recursive call
-}

expt :: Integer -> Integer -> Integer
expt b 0        = 1
expt b n 
    | n > 0     = b * expt b (n-1)  -- backward recursion
    | otherwise = error ("expt not defined for negative exponent" 
                         ++ show n)


{-  Function "expt2" computes b^n using tail recursion.  

    Time complexity:  O(n) recursive calls 
    Space complexity: O(1) with tail call optimization 
    Termination:      Argument m of expt_iter decreases by 1 
                      toward 0 inrecursive call
-}

expt2 :: Integer -> Integer -> Integer
expt2 b 0       = 1
expt2 b n
    | n > 0     = expt_iter n 1
    | otherwise = error ("expt2 not defined for negative exponent" 
                         ++ show n)
        where 
            expt_iter 0 p = p  
            expt_iter m p = expt_iter (m-1) (b*p) -- tail recursion
 

{-  Function "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
     Termination:      Argument n decreases either by one-half or 
                       by 1 toward 0 on the recursive calls
-}

expt3 :: Integer -> Integer -> Integer
expt3 b 0             = 1
expt3 b n  
    | n > 0 && even n = let exp = expt3 b (n `div` 2) in 
                            exp * exp      -- backward recursion
    | n > 0           = b * expt3 b (n-1)  -- backward recursion
    | otherwise = error ("expt3 not defined for negative exponent" 
                         ++ show n)        


-- Exercise:  Can you implement a tail recursive version of expt3?


-- Testing of expt

bases  = [2,3,6]
powers = [0,1,2,3,4,5,6,7,8,9,10,20]

result_expt = [ expt b n | b <- bases, n <- powers ]

-- Testing of expt2

result_expt2 = [ expt2 b n | b <- bases, n <- powers ]

-- Testing of expt3

result_expt3 = [ expt3 b n | b <- bases, n <- powers ]