Problem with a recursive function to find sqrt of a number

Question

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 (N < mid * mid )
     {
        value = sqrtr(N,Low,mid-1) ;


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

     }

     return value;

}

@Platinum Azure : surprisingly enough, I don't. Credits to jpalecek, who noted that the +1 part was stolen from an integer algorithm. That gives you completely the wrong boundaries, so it no longer matters how you round them. — MSalters
– MSalters, Commented May 21, 2010 at 13:11

Robert Harvey · Accepted Answer · 2010-05-20 22:39:50Z

5

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

answered May 20, 2010 at 22:39

Robert Harvey

182k48 gold badges349 silver badges516 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jive Dadson Over a year ago

Uh, how about N = 143214.4213e22? Now how do you like the test, high-low < 0.000001? See my answer.

jpalecek · Accepted Answer · 2010-05-20 22:42:37Z

4

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?

answered May 20, 2010 at 22:42

jpalecek

47.9k7 gold badges105 silver badges147 bronze badges

2 Comments

Drew Hall Over a year ago

Was thinking the same thing myself. That -1 has to go!

MSalters Over a year ago

Yup. Try sqrtr(0.0001, 0.0, 0.1) for an instant proof.

Jonathan M Davis · Accepted Answer · 2010-05-20 23:22:07Z

0

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.

edited May 20, 2010 at 23:22

answered May 20, 2010 at 22:56

Jonathan M Davis

38.5k17 gold badges76 silver badges104 bronze badges

Comments

Jive Dadson · Accepted Answer · 2012-10-04 21:08:15Z

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();
}

Collectives™ on Stack Overflow

Problem with a recursive function to find sqrt of a number

4 Answers 4

1 Comment

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related