# Binary Search for the root of a polynomial

Dubravko Zubavich

Greenhorn

Posts: 20

posted 7 years ago

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.

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: 49789

69

Dubravko Zubavich

Greenhorn

Posts: 20

posted 7 years ago

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

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: 49789

69

posted 7 years ago

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 doesn't. It is as near as I can remember to calculating PI, but I have probably got the algorithm wrong anyway.Dubravko Zubavich wrote:I don't understand how does this find a number between a given range.

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. |