Problem with a recursive function to find sqrt of a number

Below is a simple program which computes sqrt of a number using Bisection. While executing this with a call like sqrtr(4,1,4) in goes into an endless recursion . I am unable to figure out why this is happening. Below is the function :

double sqrtr(double N , double Low ,double High  )
{

     double value = 0.00;

     double mid = (Low + High + 1)/2;

    if(Low == High)
     {
        value =  High;

     }

     else if (开发者_如何学JAVAN < mid * mid )
     {
        value = sqrtr(N,Low,mid-1) ;


     }
     else if(N >= mid * mid)
     {
         value = sqrtr(N,mid,High) ;

     }

     return value;

}

You may have to put a range on your low == high comparison, i.e. high - low < .000001 for six decimal places of precision.

Apart from having a bad termination condition, how did you get this:

 else if (N < mid * mid )
 {
    value = sqrtr(N,Low,mid-1) ;

How is the mid-1 justified? Didn't you cut-and-paste some code for integer binary search?

It's rarely a good idea to rely on floating point values equaling one another. It's very easy for them to be off by a slight amount since, unlike integers, they can't represent all values in the range of values that they represent.

So, you'll likely need to do a comparison to a given precision rather than exact equality.

As pointed out in one of the comments above, you should look at the paper "What Every Computer Scientist Should Know About Floating-Point Arithmetic". It's a classic, excellent paper on the nature of floating point numbers.

There are several problems. As noted by jpalecek, it looks as though you've cut-and-pasted a (not very good) binary search routine for an indexed array without understanding how it works. Also, the termination criterion is overly strict.

I suppose this is a learning exercise, because bisection and recursion is a very poor way to solve for sqrt().

The code below works, but it is horribly slow and inaccurate.

#include <iostream>
using namespace std;

double sqrtr(double N , double Low ,double High  )
{
    // Precondition: Low and High, Low <= High, must be non-negative, and must
    // bracket sqrt(N).

     const double sqrt_mef = 1e-8; // Approximate square root of machine efficiency

     double mid = (Low + High)/2; // No +1

    if((High-Low)/(1+mid) < sqrt_mef)
     {
        return mid;
     }

     else if (N < mid * mid )
     {
        return sqrtr(N,Low,mid) ;  // No -1
     }
     else
     {
         return sqrtr(N,mid,High) ;
     }

}

int main()
{   
    double sqrt_2 = sqrtr(2.0, 0, 2.0);
    cout << sqrt_2*sqrt_2  << endl;
    getchar();
}