CODEWITHSUNDEEP
javaoptimizationpolynomial-mathbisection
user2806648
user2806648

Reputation: 15

How can I optimize bisection-method for polynomial root finding in Java?

double findaroot(double x1, double x2){ //finds the root between two values
    double gap = Math.abs(x1 - x2); //find the initial interval
    while(gap > INTERVAL) { //check for precision           
        gap = gap / 2; //halve the interval
        double x3 = x1 + gap;
        if (f(x3) == 0) { //check for symmetry
            return x3;
        } else if (Math.signum(f(x1)) == Math.signum(f(x3))){
            x1 = x3; //redefine the interval
        } else {
            x2 = x3; //redefine the interval
        }
        findaroot(x1, x2); //call again
    }
    return (x1 + x2) / 2; //return the mean
}

I am trying to find a solution for f(x)=-21x^2+10x-1 in the intervals (-143, 0.222222). The guidelines state that I should implement a bisection method to solve this. Currently this method works fine for 8 of the 10 test cases that I must pass, but it gives a "Time-limit exceeded" error for the aforementioned values. It takes 15 seconds to approximate the root given a precision level of at least "0.000001" between the intervals.

I'm not sure how I can make this more efficient without changing the method. I have already implemented Horner's method to calculate the function because Math.pow(x1, x2) was taking too long.

Upvotes: 0

Views: 1852

Answers (2)

isnot2bad
isnot2bad

Reputation: 24454

As others already said: The recursive invocation of findaroot is wrong/not required. This code works for me:

private final int NMAX = 100;

public double solve(Function f, double a, double b, double tolerance) {
    if (a >= b) throw new IllegalArgumentException("illegal interval!");

    double fa = f.value(a);
    if (Math.signum(fa) == Math.signum(f.value(b))) throw new IllegalArgumentException("solution not within interval!");

    for (int n = 0; n < NMAX; n++) {
        double c = (a + b) / 2;

        double fc = f.value(c);
        if ((fc == 0.0) || ((b - a) / 2 < tolerance)) {
            // solution found
            return c;
        }

        // adapt interval
        if (Math.signum(fc) == Math.signum(fa)) {
            a = c;
            fa = fc;
        } else {
            b = c;
        }
    }

    return Double.NaN;
}

Upvotes: 0

Rafi Kamal
Rafi Kamal

Reputation: 4600

Just remove the line findaroot(x1, x2);. You are not using the result of this recursive function call anyway.

EDIT: This is the recursive version of your code (not tested)

double findaroot(double x1, double x2){ //finds the root between two values
    double gap = Math.abs(x1 - x2); //find the initial interval
    if (gap > INTERVAL) { //check for precision           
        gap = gap / 2; //halve the interval
        double x3 = x1 + gap;
        if (f(x3) == 0) { //check for symmetry
            return x3;
        } else if (Math.signum(f(x1)) == Math.signum(f(x3))){
            x1 = x3; //redefine the interval
        } else {
            x2 = x3; //redefine the interval
        }
        return findaroot(x1, x2);
    }
    else
         return (x1 + x2) / 2; //return the mean
}

Upvotes: 1

Related Questions