import java.lang.Math;

public class ZeroFind {

   public static void main(String[] args)
   {
      FunctionDoc p = new Polynomial(new double[] {1, 0, -2});
      // This should have solution x = +/- square root of 2
      showBisection(p, 0, 2);  // sqrt(2)
      showBisection(p, 0, 1);  // no root

      p = new Polynomial(new double[] {1, -3, -3, 1});
      // This should have solution x = -1.  -1 - 3 + 3 + 1 = 0
      showBisection(p, -10.0, 10.0);

      showBisection(new TrigSum(), 0, 1);  // pi / 4
   }


   /** Shows parameters and results of bisection function. */
   static void showBisection(FunctionDoc FD, double a, double b)
   {
      System.out.println("\nLet " + FD);  // use toString implicitly
      System.out.format("Looking for a root in [%f, %f].%n", a, b);
      double root = bisection(FD, a, b, true);
      if (!Double.isNaN(root))  // Nan not equal to itself!
         System.out.println ("An approximate root is " + root);
      else
         System.out.println ("Could not find the root: Endpoints same sign.");
   }


   /** This bisection method returns the best double approximation
    to a root of FD.f.  Returns double.NaN if 
    FD.f(a) and FD.f(b) have the same sign.
    Does not require a < b.  Shows steps if showSteps.
    */
   public static double bisection(FunctionDoc FD, double a, double b,
                                  boolean showSteps) {
      if (FD.f(a) == 0)
         return a;
      if (FD.f(b) == 0)
         return b;
      if (Math.signum(FD.f(a)) == Math.signum(FD.f(b)))
         return Double.NaN;  // can't do bisection
      double c = (a + b) / 2;

      // If no f(c) is exactly 0, iterate until the smallest possible
      // double interval, when there is no distinct double midpoint.
      while (c != a && c != b) {
         if (showSteps)
            System.out.format ("a = %.17g b= %.17g diff = %.17g%n", a, b, b-a);
         if (FD.f(c) == 0) {
            return c;
         }
         if (Math.signum(FD.f(c)) == Math.signum(FD.f(a)))
            a = c;
         else
            b = c;
         c = (a + b) / 2;
      }
      return c; // double value matches an endpoint here
   }

}


class TrigSum implements FunctionDoc
 {
   public double f(double x) {
      return Math.sin(x) - Math.cos(x);
   }

   public  String toString()
   {
      return "f(x) = sin x - cos x";
   }
}


class Polynomial implements FunctionDoc {
   private double[] coef; // decreasing powers

   /** Polynomial given decreasing coefficient powers */
   public Polynomial(double[] coefficients)
   {
      coef = shortenArray(coefficients);
   }

   /** return array without leading 0's */
   public static double[] shortenArray(double[] coefficients)
   {  // not in interface - ok
      int len = coefficients.length, deg = len - 1;
      while (deg > 0 && coefficients[deg] == 0)
         deg--; // leading 0's are redundant
      double[] nums = new double[deg+1];
      for (int i = 0; i <= deg; i++)
         nums[deg - i] = coefficients[len - 1 - i];
      return nums;
   }

   public double f(double x)
   {
      double sum = 0;
      for (double c : coef)
         sum = sum * x + c;
      return sum;
   }

   public String toString()
   {
      String s = "f(x) = ";
      int deg = coef.length - 1;
      for (int i = 0; i < deg; i++)
         if (coef[i] != 0)
            s += String.format("%fx^%s + ", coef[i],  deg - i);
      return s + coef[deg];
   }
}