Интервал для метода деления пополам

Question

Мне был назначен проект для определения квадратного корня числа без использования разделов или библиотеки math.h. Проведя собственное исследование, я решил решить эту проблему, используя метод деления пополам. Я использовал часть псевдокода со страницы Bisection Википедии:

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

настроить алгоритм.

Мой код

#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 что я ошибаюсь в том, как я настраиваю мои новые интервалы. Я думаю, что если разница между этими двумя значениями отрицательная, то мне нужно нажать нижнюю границу, и если разница положительная, то мне нужно поднять верхнюю границу вниз.

Буду признателен за любые советы, которые y'all мог бы дать мне. Спасибо за ваше время.

Answer 1

условие fb - fa < 0 неправильно, потому что игнорирование ошибок с плавающей точкой, fa < fb, что a * a - x < b * b < x будет всегда верно для 0 <= a < b.

Изменение состояния на fc < 0 улучшило точность, но, к сожалению, это улучшение не позволяет программе распечатать «PASS». Для повышения точности, чтобы программа печати «PASS», удалить вредную отключающую часть

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

Удаление этого вредной ломки и добавление линии

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

непосредственно перед

return c; 

дал me

Square root is: 11111.1 
PASS 

, но, к сожалению, это не то, что вы хотите. Чтобы иметь то, что вы хотите напечатать,

#include <iomanip> 

должны быть добавлены и печатная часть должна быть

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