Как оптимизировать метод bisection для поиска полиномиальных корней в Java?

Question

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 
} 

Я пытаюсь найти решение для f (x) = - 21x^2 + 10x-1 в интервалах (-143, 0.222222). В руководящих принципах указано, что я должен реализовать метод деления пополам, чтобы решить эту проблему. В настоящее время этот метод отлично работает для 8 из 10 тестовых случаев, которые я должен пройти, но для вышеупомянутых значений он дает ошибку «превышение по времени». Для того, чтобы приблизиться к корню, требуется 15 секунд, если заданный уровень точности не менее 0,000001 между интервалами.

Я не уверен, как я могу сделать это более эффективным, не меняя метод. Я уже внедрил метод Хорнера для вычисления функции, потому что Math.pow(x1, x2) занимал слишком много времени.

Answer 1

Просто удалите строку findaroot(x1, x2);. Вы все равно не используете результат этого рекурсивного вызова функции.

EDIT: Это рекурсивная версия кода (не тестировалось)

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 
} 

Answer 2

Как и другие уже сказали: Рекурсивный вызов findaroot неправильно/не требуется. Этот код работает для меня:

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; 
}