/* Functional Programming Example -- Exponentiation
   H. Conrad Cunningham, Professor
   Computer and Information Science

   Developed for CSci 555, Functional Programming, Spring 2016

1234567890123456789012345678901234567890123456789012345678901234567890

2016-02-10: Developed from 2015 Elixir version
2019-01-29: Updated for new version of Recursion Styles notes

I adapted this exponentiation module from an Elixir version, which
was, in turn, adapted from a Lua version, which was, in turn, adapted
from the Scheme code in section 1.2.4 of Abelson and Sussman's
Structure and Interpretation of Computer Programs (SICP).

I have only tested this minimally.

Scala and functional programming highlights:
- Calls sys.error for error exits
- Uses accumulating parameters (accumulator)
- Uses double (tree) recursion
- Uses tail recursion
- States complexity measures

*/

object Expt {

    /* 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: Double, n: Int): Double = n match {
        case 0          => 1
        case m if m > 0 => b * expt1(b,m-1)
        case _          =>
            sys.error(s"Cannot raise to a negative power $n")
    }
  
    /* 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: Double, n: Int): Double = {

        // private tail recursive auxiliary, called only if n >= 0
        def exptIter(n: Int, p: Double): Double = 
	    n match {
                case 0 => p
                case m => exptIter(m-1,b*p)
            }

        if (n >= 0)
            exptIter(n,1)
        else
            sys.error(s"Cannot raise to negative power $n")
    }

    /* 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 evenxs
       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
    */

    def expt3(b: Double, n: Int): Double = {

        // private tail recursive auxiliary, called only if n >= 0
        def exptAux(n: Int): Double = n match {
            case 0                 => 1
            case m if (m % 2 == 0) => // i.e. even
                val exp = exptAux(m/2)
                exp * exp             // backward recursion
            case m                 => // i.e. odd
                b * exptAux(m-1)      // backward recursion
        }

        if (n >= 0)
            exptAux(n)
        else
            sys.error(s"Cannot raise to negative power $n")
    }

    // Should implement extensive tesing externally
    def main(args: Array[String]) {
        println(s"expt1(2.0,10)  = ${expt1(2.0,10)}")
        println(s"expt2(2.0,10)  = ${expt2(2.0,10)}")
        println(s"expt3(2.0,10)  = ${expt3(2.0,10)}")
    }

}