/** Example program that finds the zero of a function using the methods
 * of bisection and Newton's algorithm.
 * 
 * The example introduces the concept of interfaces. See the Java tutorial at
 * http://docs.oracle.com/javase/tutorial/java/index.html. Study the topic
 * Interfaces and Inheritance
 * http://docs.oracle.com/javase/tutorial/java/IandI/index.html
 *
 */
public class FindZero {

	/** Interface for a function f. The interface provides the methods
	 * to get the value of f(x) and its first derivative f'(x).
	 */
	interface Function {
		/** Returns the function value at x, i.e. f(x) */
		public double evaluate(double x);
		
		/** Returns the first derivative at x, i.e. f'(x) */
		public double derivative(double x);
	}
	
	public static void main(String[] args) {
		FindZero fz = new FindZero();
		fz.run();
	}
	
	public void run() {
		double y = 2.0;
		Function f = new InvSqrt(y);
		
		double x = findZeroBisection(f, 0.1, 1);
		System.out.println("x(Bisection)  = " + x);
		
		x = findZeroNewton(f, 0.5);
		System.out.println("x(Newton)     = " + x);
		
		System.out.println("x(Calculated) = " + 1/Math.sqrt(y));
	}

	/** Finds the zero of function f using the method of bisection.
	 * On entry the following conditions must be satisfied: f(a) < 0, f(b) > 0.
	 */
	double findZeroBisection(Function f, double a, double b) {
		double c;
		do {
			c = 0.5*(a + b);
			if (f.evaluate(c) < 0) {
				a = c; // adjust lower bound
			} else {
				b = c; // adjust upper bound
			}
		} while (Math.abs(a - b)/c > 1e-15);
		return c;
	}
	
	/** Finds the zero of function f using Newton's method. On entry x0 must be
	 * an initial estimate.
	 */
	double findZeroNewton(Function f, double x0) {
		double x1, delta;
		do {
			delta = f.evaluate(x0)/f.derivative(x0);
			x1 = x0 - delta;
			x0 = x1;
		} while (Math.abs(delta) > 1e-15);
		return x1;
	}
	
	/** Used to find the solution of x=1/sqrt(y) for given y.
	 * 
	 * Implements the function f(x) = x*x - 1/y and its derivative
	 * f'(x) = 2*x
	 */
	private class InvSqrt implements Function {
		
		double y;
		
		private InvSqrt(double y) {
			this.y = y;
		}
		
		public double evaluate(double x) {
			return x*x - 1/y;
		}
		
		public double derivative(double x) {
			return 2*x;
		}
	}
}