// Interpolacja odwrotna
// www.algorytm.org

public class Main {

	// Interpolacja oparta o 3 węzły:
	private static double a = -2,b= -1,c = 4;

	public static void main(String[] args) {
		// Szukamy miejsce zerowe funkcji x^3 - 1 
		double x = inverseInterpolation();
		System.out.println("Miejsce zerowe w x="+x+" f(x)="+ function(x));
	}	

	// interpolacja odwrotna
	public static double inverseInterpolation(){
		double x = 100;
		while(Math.abs(function(x)) > 1E-20){
			x = (lagrangeInterpolation(new double[]{function(a),function(b),function(c)},
					new double[]{a,b,c},0.0));
			a = b;
			b = c;
			c = x;
		}
		return x;
	}

	// funkcja x^3 - 1 
	public static double function(double x){
		return Math.pow(x, 3) - 1;
	}

	// interpolacja Lagrange'a
	public static double lagrangeInterpolation(double[] xs, double[] ys, double x ){ 
		double t; 
		double y = 0.0; 

		for(int k = 0; k< xs.length; k++){ 
			t = 1.0; 
			for(int j = 0; j < xs.length ; j++){ 
				if(j != k ){ 
					t=t*((x-xs[j])/(xs[k]-xs[j]));  
				} 
			} 
			y += t*ys[k]; 
		} 
		return y; 
	}

}