• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Binary Search for the root of a polynomial

 
Dubravko Zubavich
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 48382
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
    Posts: 20
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 48382
    56
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic