Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Binary Search for the root of a polynomial

Dubravko Zubavich
Greenhorn
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
Posts: 50749
83
Please write out the algorithm, in little steps, like

• 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
Campbell Ritchie wrote:Please write out the algorithm, in little steps, like

• 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: 50749
83
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.

 Consider Paul's rocket mass heater.