/**
 * A3Examples contains some methods whose correctness is to be examined in
 * Assignment 3
 */
public class A3Examples {
  
  /**
   * pow(b,p) returns b^p.
   * @param b an integer base to exponentiate.
   * @param p a natural number power to exponentiate to.
   * @return b^p.
   * Precondition: b is an integer and p is a natural number.
   * Postcondition: b^p is returned.
   */
  public static int pow(int b,int p) {
    int bToTheP = 1;
    int i = 0;
    while (i != p) {
      bToTheP *= b;
      ++i;
    }
    return bToTheP;
  }
  
  /**
   * recPow(b,p) returns b^p (more efficiently).
   * @param b an integer base to exponentiate.
   * @param p a natural number power to exponentiate to.
   * @return b^p.
   * Precondition: b is an integer and p is a natural number.
   * Postcondition: recPow(b,p) terminates, and when it does b^p is returned.
   */
  public static int recPow(int b, int p) {
    int bToTheP = 1;
    
    if (p % 2 == 1) {
      bToTheP = b;
    }
    
    if (p < 2) {
      return bToTheP;
    }
    
    // p/2 is integer division
    return bToTheP * recPow(b, p/2) * recPow(b,p/2);
  }
  
  /**
   * div(m,n) returns quotient and remainder for m/n
   * @param m a natural number dividend.
   * @param n a positive natural number divisor.
   * @return [q,r] such that m = qn + r and 0 <= r < n.
   * Precondition: m is a natural number, n is a positive natural number.
   * Postcondition: [q,r] is returned and m = qn + r, 0 <= r < n.
   */
  public static int[] div(int m, int n) {
    int[] quotRem = {0,0}; // initialized to [0,0]
    while (m != quotRem[0] * n + quotRem[1]) {
      if (quotRem[1] < n-1) {
        ++quotRem[1];
      }
      else {
        ++quotRem[0];
        quotRem[1] = 0;
      }
    }
    return quotRem;
  }
  
  /**
   * cube(n) returns the cube of natural number n.
   * @param n is a natural number.
   * @return n^3.
   * Precondition: n is a natural number.
   * Postcondition: cube(n) terminates, and when it does n^3 is returned.
   */
  public static int cube(int n) {
    if (n == 0) {
      return n;
    }
    
    return 1 + 3 * (n-1) + 3 * (n-1) * (n-1) + cube(n-1);
  }
  

}