var NumberTheory = {};

/**
 * @param {number} n
 * @param {number} k
 */
NumberTheory.binomial = function(n, k) {
  if (n === k) return 1;
  if (k === 1) return n;
  return binomial(n - 1, k) + binomial(n - 1, k - 1);
};

/**
 * Prototype that stores information about a given polynomial.
 * @constructor
 * @param {string|Polynomial} data The polynomial to parse.
 * @return {Polynomial}
 */
function Polynomial(data) {
  // Support providing already existing Polynomials.
  this.polynomial = data instanceof Polynomial ? data.polynomial : data;
}

/**
 * Rank all coefficients in the polynomial and return the largest.
 * @return {number}
 */
Polynomial.prototype.getLargestCoefficient = function() {
  var re = /(\d+)/g, match, max = 0;
  while(match = re.exec(this.getPolynomial()))
    max = Math.max(max, match[1]);
  return max;
};

/**
 * Returns the polynomial as plain text.
 * @return {string}
 */
Polynomial.prototype.getPolynomial = function() {
  return this.polynomial;
};

/**
 * Replaces x for a given value and evaluates the polynomial as a JavaScript expression.
 * @param {number} val The value for x.
 */
Polynomial.prototype.insert = function(val) {
  return eval(this.getPolynomial().replace(/x/g, val.toString()));
};

/**
 * Sigma sum of a polynomial from start to end.
 * @param {number} start The starting index.
 * @param {number} end The ending index.
 */
Polynomial.prototype.sum = function(start, end) {
  var result = 0;
  var i = start;

  while (i <= end) {
    result += this.insert(i);
    i += 1;
  }

  return result;
};

/**
 * Product of a polynomial from start to end.
 * @param {number} start The starting index.
 * @param {number} end The ending index.
 */
Polynomial.prototype.product = function(start, end) {
  var result = start;
  var i = start;

  while (i <= end) {
    result *= this.insert(i);
    i += 1;
  }

  return result;
};

Polynomial.prototype.limit = function(val) {
  // Might consider shrinking dx incrementally to get good approximation.
  // Might also consider limiting from top and bottom of x.
  // Using analysis of dy we should also be able to detect convergence to infinities.
  return this.insert(val + 10e-6);
};

/**
 * To differentiate we just insert an arbitrary small value as the delta x and evaluate it.
 * @param {number} val The value to differentiate for.
 */
Polynomial.prototype.differentiate = function(val) {
  return (this.insert(val + 10e-6) - this.insert(val)) / 10e-6;
};


/**
 * Prototype that stores information about a given equation.
 * @constructor
 * @return {Equation}
 */
function Equation(data) {
  // Support providing already existing Equations.
  data = data instanceof Equation ? data.polynomial : data;
  // Move everything over to the left side of the equation and set equal to zero.
  data = data.replace(/(.*)=(.*)/, '$1-($2)');
  // We internally store equations as a polynomial set equal to zero.
  this.polynomial = new Polynomial(data);
}

/**
 * Evaluates the left side polynomial of the equation.
 */
Equation.prototype.insert = function(val) {
  return this.polynomial.insert(val);
};

/**
 * Solves the equation using Newtons method.
 * @param {number=} errorTreshold The error treshold to stop at.
 * @param {number=} guess The initial guess.
 * @param {number=} maxIterations The max number of iterations before giving up.
 * @return {number}
 */
Equation.prototype.solve = function(errorTreshold, guess, maxIterations) {
  // Set default error treshold value.
  errorTreshold = errorTreshold || 10e-6;

  // Pick largest coefficient as initial guess. It gives some basic
  // understanding over what scale of numbers we are dealing with.
  guess = guess || this.polynomial.getLargestCoefficient();

  // Set default value for maximum number of iterations before timeout.
  maxIterations = maxIterations || 1000;

  // Loop requires number or it will stop prematurely.
  var error = errorTreshold + 1;

  // Store iterations to detect timeouts.
  var iteration = 0;

  // Run iterations of Newtons method.
  while (error >= errorTreshold && iteration <= maxIterations) {
    error = this.insert(guess) / this.polynomial.differentiate(guess);
    guess = guess - error;
    iteration += 1;
  }

  // Return our final guess.
  return guess;
};