/**
 * @author Roman Rietmann
 *
 * Aitken Verfahren
 *
 */
public class NewtonVsAitken {

	private static double startX = 20;
	private static double tolerance = 0.000000000001;
	static double[] koef = {-2, 0, 4, 1};
	private static Polynom p = new Polynom(koef);
	private static Newton nt = new Newton(startX, p);
	private static Register r = new Register();
	private static Aitken ai = new Aitken(r, p);

	public static void main(String[] args) {
		int i = 0;
		while(Math.abs(p.f(nt.nextVal())) > tolerance) {
			r.moveLeft(nt.currentVal());
			if(i >= 2) {
				ai.nextVal();
			}
			System.out.println("Step: " + i + " ---> Newton -> x: " + nt.currentVal() + " --- Aitken -> x: " + ai.currentVal());
			i++;
		}
	}
}

class Aitken {
	Register r;
	Polynom p;
	double pnd = 0;

	Aitken(Register r, Polynom p) {
		this.r = r;
		this.p = p;
	}

	double nextVal() {
		double p0 = r.reg[0];
		double p1 = r.reg[1];
		double p2 = r.reg[2];
		pnd = p0 - (p1 - p0) * (p1 - p0) / (p2 - 2 * p1 + p0);
		return pnd;
	}

	double currentVal() {
		return pnd;
	}
}

class Newton {
	double x;
	double oldX = 0;
	Polynom p;

	Newton(double startX, Polynom p) {
		this.x = startX;
		this.p = p;
	}

	double nextVal() {
		x = oldX - p.f(x) / p.steigung(x);
		oldX = x;
		return x;
	}

	double currentVal() {
		return oldX;
	}
}

class Register {
	double[] reg = new double[3];

	void moveLeft(double n) {
		reg[0] = reg[1];
		reg[1] = reg[2];
		reg[2] = n;
	}
}

class Polynom {
	private double deltaX = 0.01;
	double[] koef;

	Polynom(double[] koef) {
		this.koef = koef;
	}

	public double steigung(double x) {
		return (f(x + deltaX / 2) - f(x - deltaX / 2)) / deltaX;
	}

/*	public double f(double x) {
		double result = 0;
		for(int i = 0; i < koef.length; i++) {
			result = result + Math.pow(x, i) * koef[i];
		}
		return result;
	}
*/

	public double f(double x) {
		//return Math.exp(-x) + Math.pow(2, -x) + 2 * Math.cos(x) - 6;
		return Math.PI;
	}
}