Binary Search for the root of a polynomial

[Dubravko Zubavich]

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]

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]

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]

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.