/**
   Boston University, Department of Computer Science
   CS 112 Lab 01: Recursion 
   Teaching Fellow: Diane H. Theriault, deht@cs.bu.edu
 */

public class PowerComputer{

  /**
   * Empty constructor 
   */
  PowerComputer() {}
  
  /**
   * Compute f(x,n) = x^n
   */
  public double exponentiate(int x, int n)
  {
    mNumIterations = 0;
    //return exponentiateLinear(x,n);
    //return exponentiateIncorrectLogarithmic(x,n);
    return exponentiateLogarithmic(x,n);
  }

  public int getNumIterations()
  {
    return mNumIterations;
  }
  
  private double exponentiateLinear(int x, int n)
  {
    mNumIterations ++;
    if(n == 0)
    {
      return 1;
    }
    
    return x*exponentiateLinear(x,n-1);
  }

  private double exponentiateIncorrectLogarithmic(int x, int n)
  {
    mNumIterations ++;
    if(n == 0)
    {
      return 1;
    }
        
    if(n % 2 == 1)
    {
      n = n-1;
      return x * exponentiateIncorrectLogarithmic(x, n/2) * exponentiateIncorrectLogarithmic(x,n/2);
    }
    else
    {
      return exponentiateIncorrectLogarithmic(x, n/2) * exponentiateIncorrectLogarithmic(x,n/2);
    }
  }

  private double exponentiateLogarithmic(int x, int n)
  {
    mNumIterations ++;
    if(n == 0)
    {
      return 1;
    }
        
    if(n % 2 == 1)
    {
      n = n-1;
      double result = exponentiateLogarithmic(x, n/2);
      return x * result * result;
    }
    else
    {
      double result = exponentiateLogarithmic(x, n/2);
      return result * result;
    }
  }

  private int mNumIterations;
}