Binary Search with nextafter()

Question

I input an double n and am trying to find the root by binary search. the break-condition with epsilon are kind of long and i was thinking about using nextafter() to compute the result with high precision.

double lower = 1, upper = n, mid, midSquared;
while (nextafter(lower,upper) < upper) {
    mid = (l + u)/2.;
    midSquared = mid * mid;
    if (midSquared < n) lower = mid;
    else upper = mid;
}

Am I guaranteed that that way my loop terminates? This actually is about mid. Will mid take a value between lower and upper bound, when there is a displayable one? This seems to me as a nice approach because it matches the index comparison binary search on a sorted list. (Lower index + 1 < Upper index)

Answer 1

Initializing lower to 0 and upper to a minimum of 1 will allow your code to find square roots for values < 1.

I would do the error checking on the return value from nextafter if you aren't doing range validation on n. Check for NaN and HUGE_VAL.

double lower = 0;
double upper = (n < 1) ? 1 : n;
double next = nextafter(lower, upper);

while (!isnan(next) && (next < upper) && (next != HUGE_VAL))
{
    double mid = (lower + upper) / 2.;
    double midSquared = mid * mid;
    if (midSquared < n)
    {
        lower = mid;
    }
    else
    {
        upper = mid;
    }
    next = nextafter(lower, upper);
}

And if you really want to be sure, you could put a counter on the loop as well and abort if it does too many loops.

int count = 0;
while (!isnan(next) && (next < upper) && (next != HUGE_VAL) && (count < 1000))
{
    count++;
    double mid = (lower + upper) / 2.;
    ...