Interval for bisection method

Question

I've been assigned a project to determine the square root of a number without using division or the math.h library. Upon doing my own research I've decided to tackle the problem by using the bisection method. I used the pseudo code portion from the Bisection Wikipedia page:

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

to setup the algorithm.

My Code

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

The output I am currently getting for my professor's test case in main is

Square root is: 1.23457e+08
FAIL

When the correct output should be

Square root is: 11,111.11106
PASS

I believe that I am going wrong in the way that I setup my new intervals. My thinking is that if the difference between the two values is negative, then I need to push the lower bound up, and if the difference is positive, then I need to bump the upper bound down.

I would appreciate any advice y'all could give me. Thank you for your time.

"without using division" *0.5 Trololol. =D Define "division" I guess. — Baum mit Augen
Perhaps trying your function on a smaller number will allow you to debug it to figure out what is going on. — mah
Your next choice of interval should be based on whether c is positive or negative. — user253751
@mah I've tried using smaller numbers like 9 or 16, but the output is still incorrect. When I was printing out the intervals after each iteration, I found that the upper bound was constantly decreasing, even going past what I knew the actual square root was. — Austin
@ immibis Did you mean fc, the value of the function f(c) = c^2 - x ? As I understand it (and as I've implemented it), c should never be negative. — Austin

MikeCAT MikeCAT · Accepted Answer · 2016-06-02T00:34:37

The condition fb - fa < 0 is wrong because ignoring floating-point errors, fa < fb, which is a * a - x < b * b < x will be always true for 0 <= a < b.

Changing the condition to fc < 0 improved the accuracy, but unfortunately this improvement coundl't make the program print "PASS". To improve the accuracy to have the program print "PASS", delete the harmful breaking part

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

Removing this harmful breaking and adding the line

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

just before

return c;

gave me

Square root is: 11111.1
PASS

but unfortunately this is not what you want. To have what you want printed,

#include <iomanip>

should be added and the printing part should be

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

Interval for bisection method

1 Answers