C++ Square Root Function Bug

Question

I have a c++ algorithm that calculates the square root of an integer. The program works with the exception of a single flaw. It is unable to calculate the square root of a number that is below 1. For example, it cant calculate the square root of .5 or .9 or .0000001 etc. but works as planned for all other situations. I have X set so it doesn't allow a negative input, but I still can't see why it wont return a value for anything less than 1.

include <iostream>
#include <cmath>
#include <cassert>

using namespace std;

double squareroot(double x)

{ /* computes the square root of x */

  /* make sure x is not negative .. no math crimes allowed! */
    assert(x >= 0);
    if (x == 0) return 0;

    /* the sqrt must be between xhi and xlo */
    double xhi = x;
    double xlo = 0;
    double guess = x / 2;

    /* We stop when guess*guess-x is very small */

    while (abs(guess*guess - x) > 0.000001)
    {
        if (guess*guess > x)  xhi = guess;
        else xlo = guess;
        guess = (xhi + xlo) / 2;
    }

    return guess;
}

/* Test Stub */


int main()
{
    double testvalue;
    cout << "\n Enter a TestValue= ";
    cin >> testvalue;
    cout << endl;
    double testresult = squareroot(testvalue);
    cout << "\n Square Root= " << testresult << "\n";
}

Thanks for the help! I was able to solve the problem by using the following:

if (x<1) {
    xhi = 1;
    xlo = x;
    guess = (x + 1) / 2;
}

As an aside, testing for equality on floating point values is a no-no. Use a discrete distance test instead: `bool IsEqual(double a, double b) { return std::fabs(a - b) < 0.000001; }` — Casey, Jan 14 '16 at 05:12
I'd start by making sure noting is going back to ints by using "floating notaion" throughout (i.e. `guess = (xhi + xlo) / 2.0`) — John3136, Jan 14 '16 at 05:12
Check the math, not the code. Note that when `x < 1` the `if (guess*guess > x)` will always go the `else` route. — dxiv, Jan 14 '16 at 05:17
Your problem description is unclear. You want to compute square roots of an integer, and then have trouble calculating the square root of a value greater than zero and less than one. AFAIK, there are very few integers that are both greater than zero and less than one. — Peter, Jan 14 '16 at 05:21
If you want a high precision answer, changing your `guess = ...` code to `double next_guess = ...; if (next_guess == guess) break; guess = next_guess;` iterates until you achieve stability (for any algo, you should always think about whether that's guaranteed to happen though). — Tony Delroy, Jan 14 '16 at 05:21

score 10 · Accepted Answer · answered Jan 14 '16 at 05:17

The square root of 0.5 is ~0.7. Your logic is guessing a smaller number if the check fails. What you need to do is add an extra detection layer to see if the number is < 1, and then modify the flow to increase the next guess instead of decreasing it.

Ilyas y. · Answer 2 · 2016-01-14T06:45:03.273

2

In case of x<1 you need change initial boundaries because square root locates not between 0 and x but between x and 1

double xhi, xlo, guess;
if (x > 1){
    xhi = x;
    xlo = 0;
    guess = x / 2;
}
else{
    xhi = 1;
    xlo = x;
    guess = (x + 1) / 2;
}

edited Jan 14 '16 at 06:45

answered Jan 14 '16 at 05:41

Ilyas y.

167
7

2

That's the right answer as far as math goes, but for the code to work you need to remove those `double` declarations. Just `xhi = x;` will (correctly) initialize the `double xhi;` declared outside the `if`, as opposed to defining a local `double xhi = x;` inside the `if` block which would be of no use or consequence outside the block. – dxiv Jan 14 '16 at 05:51

R Sahu · Answer 3 · 2016-01-14T05:54:27.977

Add some debugging output. That will help you understand why the program never converges to a solution when x < 1.0.

while (abs(guess*guess - x) > 0.000001)
{
    if (guess*guess > x)
    {
       cout << "Changing xhi\n";
       xhi = guess;
    }
    else
    {
       cout << "Changing xlo\n";
       xlo = guess;
    }

    guess = (xhi + xlo) / 2;
    cout << "guess: " << guess << endl;
}

If you follow the Newton-Raphson method, the program will converge faster. Also, it works regardless of whether x is greater than or less than 1.

double squareroot(double x)
{
   /* make sure x is not negative .. no math crimes allowed! */
   assert(x >= 0);
   if (x == 0) return 0;

   double guess = x / 2;
   while (abs(guess*guess - x) > 0.000001)
   {
      double dx = 0.5*(guess*guess -x)/guess;
      guess -= dx;
      cout << "guess: " << guess << endl;
   }

   return guess;
}

C++ Square Root Function Bug

3 Answers3

Linked