如何優化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 
} 

我正在嘗試在間隔（-143,0.2222222）中找到f（x）= - 21x^2 + 10x-1的解。準則規定，我應該實施一種二分法來解決這個問題。目前這種方法對於我必須通過的10個測試用例中的8個正常工作，但是它給出了上述值的「超出時間限制」錯誤。假定間隔之間的精度等級至少爲「0.000001」，則需要15秒來近似根。

我不知道如何在不更改方法的情況下使此效率更高。我已經執行霍納的方法來計算功能，因爲Math.pow(x1, x2)花費的時間太長。

Answer 1

只要刪除行findaroot(x1, x2);。無論如何你都沒有使用這個遞歸函數調用的結果。

編輯：這是你的代碼的遞歸版本（沒有測試）

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