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

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("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(b1: Double, n1: Int, p: Double): Double = n1 match {
      case 0 => p
      case m => exptIter(b1,m-1,b1*p)
    }

    if (n >= 0)
      exptIter(b,n,1)
    else
      sys.error("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 exptIter(b1: Double, n1: Int): Double = n1 match {
      case 0                 => 1
      case m if (m % 2 == 0) => // i.e. even
        val exp = exptIter(b1, m/2)
        exp * exp               // backward recursion
      case m                 => // i.e. odd
        b1 * exptIter(b1,m-1)  // backward recursion
    }
    
    if (n >= 0)
      exptIter(b,n)
    else
      sys.error("Cannot raise to negative power " + n )
  }

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

}