二分法の間隔

Question

私は、除算やmath.hライブラリを使わずに数値の平方根を求めるプロジェクトを割り当てられています。私自身の研究をする際に、私は二分法を使って問題に取り組むことに決めました。セットアップにアルゴリズムを

https://en.wikipedia.org/wiki/Bisection_method#Example:_Finding_the_root_of_a_polynomial

：私は二分Wikipediaのページから擬似コード部分を使用しました。

マイコード

#include <iostream> 
#include <cmath> 
#include <stdlib.h> 

using namespace std; 

void __attribute__((weak)) check(double alt_sqrt(double)); 

//default check function - definition may be changed - will not be graded 
void __attribute__((weak)) check(double alt_sqrt(double)) 
{ 
    if(alt_sqrt(123456789.0) == sqrt(123456789.0))cout << "PASS\n"; 
    else cout << "FAIL\n"; 
    return; 
} 

//change this definition - will be graded by a different check function 
double my_sqrt(double x) 
{ 
    int i = 0; 
    double a = 0.0;   // Lower Bound 
    double b = x + 1;  // Upper Bound 
    double c = 0.0;   // Guess for square root 
    double error = 0.00001; 
    double fc = 0.0; 
    while(i < 10000) 
    { 
     c = (a+b)*0.5; 
     fc = c * c - x; 
     if(abs(fc) < error || (b-a)*0.5 < error)  // Check for solution 
     { 
      cout << "Square root is: " << c << endl; 
      break; 
     } 
     if(fc < 0)  // Setup new interval 
     { 
      a = c; 
      cout << "a is: " << a << endl; 
     } 
     else b = c; 
     cout << "b is: " << b << endl; 
     i++; 
    } 
    return c; 
} 

//Do not change this function 
int main() 
{ 
    check(my_sqrt); 
    return 0; 
} 

私は現在、メインの私の教授のテスト・ケースのために取得しています出力は

Square root is: 1.23457e+08 
FAIL 

で正しい出力が

Square root is: 11,111.11106 
PASS 

Iであるべきときセットアップの方法で間違っていると思う私の新しい間隔。私の考えは、2つの値の差が負の場合、下限を押し上げる必要があり、その差が正の場合、上限を下げる必要があるということです。

私はあなたが私に与えることができるすべてのアドバイスに感謝します。あなたの時間をありがとう。

Answer 1

a * a - x < b * b < xが0 <= a < bのために常にtrueになりますで、浮動小数点エラーを無視しているためfb - fa < 0が間違っている状態、fa < fb、。

条件をfc < 0に変更すると精度は向上しましたが、残念ながらこの改善はプログラムの印刷を「パス」にしません。 、プログラムの印刷「PASS」を持つように精度を向上させる、この有害な破壊の取り外しと

return c; 

を与えた直前ライン

cout << "Square root is: " << c << endl; 

を追加

if(abs(fc) < error || (b-a)*0.5 < error)  // Check for solution 
    { 
     cout << "Square root is: " << c << endl; 
     break; 
    } 

有害な破断部分を削除するには私

Square root is: 11111.1 
PASS 

しかし、残念ながらこれはあなたが望むものではありません。 "除算を使わずに" *あなたが印刷したいものを持っている、

#include <iomanip> 

を追加する必要がありますし、印字部分が

std::cout.imbue(std::locale("")); 
cout << fixed << setprecision(5) << "Square root is: " << c << endl;