//
// 
//  
// Brent root finding method
//  
//  
import java.util.*;
import java.awt.*;
import java.applet.Applet;
import java.awt.event.*;
import javax.swing.*;

class fc extends f_x
{
public double func(double x)
{return (x+3)*(x-1)*(x-1);}
}

public class NA13F
{

public static double brent(f_x f,double xl,double xu)
{
    // roots of the nonlinear equation: Brent method
    // referances : Numerical Methods for Engineers, 
    // Steven C. Chapra, Raymond P. Chanale, sixth edition
    // Mc-Graw-Hill	
    // Moler,C.B. Numerical Computing with MATLAB, SIAM, 
    // Philedelphia, 2004
    double eps=2.22044604925031e-16;
    double tol=0.000001;
    double s,p,q,r;
    double m;
    double a=xl;double b=xu;double fa=f.func(a);double fb=f.func(b);
    double c=a;double fc=fa;double d=b-c;double e=d;
    int MAXITER=100;
    for(int i=0;i<MAXITER;i++)
    {
    if(fb==0) return b;
    if(Math.signum(fa)==Math.signum(fb))
    {a=c;fa=fc;d=b-c;e=d;
    if(Math.abs(fa)<Math.abs(fb))
    {c=b;b=a;a=c;fc=fb;fb=fa;fa=fc;}
    m=0.5*(a-b);
    tol=2*eps*Math.max(Math.abs(b),1);
    if(Math.abs(m)<=tol || fb==0) return b; //exit
    if(Math.abs(e)>=tol && Math.abs(fc)>Math.abs(fb))
    {s=fb/fc;
     if(a==c) {p=2*m*s;q=1-s;} //secant method
     else     {q=fc/fa;r=fb/fa;p=s*(2*m*q*(q-r)-(b-c)*(r-1));//Ýnverse quadratic interpolation
               q=(q-1)*(r-1)*(s-1);
              }
     if(p>0) q=-q;
     else    p=-p;
     if(2*p<(3*m*q-Math.abs(tol*q)) && p<Math.abs(0.5*e*q))
     {e=d;d=p/q;}
     else
     {d=m;e=m;}
     }
     c=b;fc=fb;
     if(Math.abs(d)>tol) {b=b+d;}
     else {b=b-Math.signum(b-a)*tol;}
     fb=f.func(b);      
    }
    }
    return b;
    }
    
 
     public static void main (String args[])  
     { 
     double a,b;
     
     a=Double.parseDouble(JOptionPane.showInputDialog(" Enter lower limit of the function a : "));
     b=Double.parseDouble(JOptionPane.showInputDialog(" Enter upper limit of the function  b : "));
     double r;
     fc f=new fc();
     r= brent(f,a,b);
     JOptionPane.showMessageDialog(null," root value (x)  : "+r+"\nfunction value f(x) : "+f.func(r),
     "Root finding by using brent method : ",JOptionPane.PLAIN_MESSAGE);
     System.exit(0);
     } 
}
