/**
 * An implementation of the expt function, written by the crazy folks
 * in CSC323 2010S at Grinnell College.
 *
 * Copyright (c) The crazy folks in CSC 323 2010S
 * Released under GPL 3.0, so hah!
 */

#include "expt.h"

/**
 * Compute x*x
 */
static double
square (double x)
{
  return x*x;
} /* double */

/**
 * Compute x^n.
 *   Preconditions:
 *     n >= 0
 *     Types are correct
 *   Postconditions:
 *     The result is x^n, or at least a reasonable approximation
 *     given the limitations of the double represenation.
 *   Strategy:
 *     Uses a divide-and-conquer approach that is intentionally
 *     unreadable to novices.
 */
double
expt (double x, int n)
{
  if (n == 0)
    return 1.0;
  if ((n%2) == 0)
    return square (expt (x, n/2));
  return x * expt (x, n-1);
} /* expt */