File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Binary Search for the root of a polynomial Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Binary Search for the root of a polynomial" Watch "Binary Search for the root of a polynomial" New topic
Author

Binary Search for the root of a polynomial

Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
I have to write a method that calculates the root of a polynomial. But that root has to be found using binary search. The method specifications are write a method which returns a double value which is the root of the polynomial. The method's parameters are the polynomial, a double value x, double value z and a double value epsilon.

Precondition : epsilon is greater than zero.
and f(x) <= 0 <= f(z)

We have to find a value y between x and z, where f(y) = 0, which is the root of polynomial. The difference between return value and real root is no more than epsilon.

What I do not understand about this problem is how can a search for one double number between two double numbers using binary search.

Here two of my methods, the evaluate method and finding the root on which I am working on:

public double evaluate(double x)
{
double p = 0;
for (int i = degree; i >= 0; i--)
p = coef[i] + (x * p);
return p;
}

// return root
public static double calculateRoot(Polynomial f, double x, double z, double epsilon)
{
if(epsilon < 0)
{
System.out.println("Epsilon cannot be negative. ");
return 0;
}


if(!((f.evaluate(x) <= 0) && (0 <= f.evaluate(z))))
{
System.out.println("Pre-condition violated!! ");
return 0;
}


// Not sure what to do here.....

}


Any hints as to how to approach this problem.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39393
    
  28
Please write out the algorithm, in little steps, like

  • Start with sum = 0
  • Start with counter = 1
  • Divide 1 by counter, and add to sum.
  • Multiply counter by -1
  • Repeat until difference is infinitesimal
  • Multiply sum by 4
  • Then you will find it easy to work out what to code.
    Dubravko Zubavich
    Greenhorn

    Joined: Mar 04, 2009
    Posts: 20
    Campbell Ritchie wrote:Please write out the algorithm, in little steps, like

  • Start with sum = 0
  • Start with counter = 1
  • Divide 1 by counter, and add to sum.
  • Multiply counter by -1
  • Repeat until difference is infinitesimal
  • Multiply sum by 4
  • Then you will find it easy to work out what to code.


    I don't understand how does this find a number between a given range.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    Dubravko Zubavich wrote:I don't understand how does this find a number between a given range.
    It doesn't. It is as near as I can remember to calculating PI, but I have probably got the algorithm wrong anyway.

    It is an example of what you should write down, and when you have that sort of thing (pseudo-code) it is usually easy to convert to code.
     
    It is sorta covered in the JavaRanch Style Guide.
     
    subject: Binary Search for the root of a polynomial