Using binary search to find the square root of a number in C

Question

Trying to work out the square root of a number using binary search, however my implementation of it is not working and i'm not sure why - any help appreciated, thank you

Heres my code. 'end' being the value of the number I want to be square rooted

 while(start <= end) {
   float mid = ((start + end) / 2);
   printf("\nhalving mid");

   if(mid * mid == end){
      sqrt = mid;
      printf("\nsqrt = %d", sqrt);
   }
   if(mid * mid < end){
     start = mid + 1;
     sqrt = mid; 
     printf("\nsqrt: %d", sqrt);
   }
   else{
     start = mid - 1;
   }
 }

There is no input I'm using it as a square root function where 'end' is the number I want to find the square root of — LC12382, Nov 28 '16 at 16:53
Your code will print values smaller that the square root, continue past a direct hit, and get stuck in an endless loop. I'm sorry to have to tell you this, but you must tackle some simpler exercises before you attempt this. — Beta, Nov 28 '16 at 16:58
If this isn't just for fun or training use a Newton iteration which converges much faster. (ignoring Math.sqrt for a moment). — Henry, Nov 28 '16 at 17:03
Use a debugger or print the interval ends in every step to see why the dynamics of your implementation stall at some point. Going up by one, going down by one, repeat infinitely. — Lutz Lehmann, Nov 28 '16 at 17:09

score 8 · Answer 1 · answered Nov 28 '16 at 17:01

In addition to the logic problems in your code, it is not a good practice to compare floating point numbers.

mid * mid == end will probably always fail, even for sqrt(9) because it is very difficult to test floating-point numbers for equality.

Look at this implementation using a range (epsil) instead of comparison:

static float my_sqrt(float num)
{
    double start = 0.0;
    double end = num;
    double sqrt = 0.0;
    double epsil = 0.000001;

    while (start <= end)
    {
        double mid = ((start + end) / 2);

        sqrt = mid;
        printf("sqrt = %f\n", sqrt);
        if (fabs(mid * mid -num) <= epsil)
        {
            break;
        }
        else if (mid * mid < num)
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }
    return sqrt;
}

Do you have a special reason for not using `DBL_EPSILON` from `float.h`? — deamentiaemundi, Nov 28 '16 at 17:35
the idea was to show that precision is in the programmer's hands. It sounds like a good idea. — eyalm, Nov 28 '16 at 17:42

score 1 · Answer 2 · answered Nov 28 '16 at 17:12

I am not fixingyour code, just explaining how I would write it.

Use an invariant that expresses the bracketing of the solution:

low² <= N < high²

Then taking an intermediate value mid, the test

mid² <= N

allows to choose among

low² <= N < mid² and mid² <= N < high²

and narrow down the search interval.

The iterations can stop when the search interval is a small as the floating-point representation allows (i.e. 23 bits for single precision). You can stop when low == high.

To establish the invariant,

low= 0, high= N

can do, provided that 0 <= N < N². This doesn't work when N <= 1. A quick and dirty workaround is to set high= 1.

low= 0
if N >= 1:
    high= N
else:
    high= 1

while low < high:
    mid= 0.5 * (low + high)
    if mid * mid <= N:
        high= mid
    else:
        low= mid

IMO, testing for equality mid² == N, then inequality mid² < N is counter-productive. You may be tempted to think that early termination when N is a perfect square allows to shorten the execution time. But in reality, most of the input numbers are not perfect squares and you will be performing two tests instead of one, making the program slower on average.

Lutz Lehmann · Answer 3 · 2016-11-28T17:04:24.233

0

Certainly the last line should be

 end = mid - 1;

conforming to the three cases

start..mid-1, mid, mid+1..end

And you should separate the number num that you want to compute the square root of and the end end of the search interval.

Of course you will also get a problem when the square root is not an integer. Then at some point it will fall inside one of the intervals (mid-1, mid) or (mid, mid+1) and thus outside of your algorithm.

Thus you need to separate the cases as

[start, mid] (mid, mid+1), [mid+1,end]

if you want to stay with integer boundaries. The middle case is

 ( mid*mid> num ) && ( (mid+1)*(mid+1) < num )

edited Nov 28 '16 at 17:04

answered Nov 28 '16 at 16:49

Lutz Lehmann

25,219
2
22
51

I've tried that before however it does not work when 'end' is the value of the number I want to find the square root for, I just get the value 1 returned every time – LC12382 Nov 28 '16 at 16:54
Of course you will get a problem when the square root is not an integer. – Lutz Lehmann Nov 28 '16 at 16:57
You will also get non-sensical results if you change the input during the algorithm. Separate the input that stays constant during the search from the variable ends of the search interval. – Lutz Lehmann Nov 28 '16 at 17:05

score 0 · Answer 4 · answered Jul 15 '18 at 21:39

0

You should replace your last line with

end = mid -1

in the else snippet

answered Jul 15 '18 at 21:39

Prathu Baronia

125
5

score -1 · Answer 5 · answered Apr 08 '18 at 20:13

public int sqrt(int x) {
    if (x == 0)
        return 0;
    int left = 1, right = Integer.MAX_VALUE;
    while (true) {
        int mid = left + (right - left)/2;
        if (mid > x/mid) {
            right = mid - 1;
        } else {
            if (mid + 1 > x/(mid + 1))
                return mid;
            left = mid + 1;
        }
    }
}

Using binary search to find the square root of a number in C

5 Answers5

Linked