How to Correctly Round a Square Root Function?

Question

I am currently working on a Java math library which will include a variety of correctly rounded functions (i.e. sqrt, cbrt, exp, sin, gamma, and ln). I have already used the Babylonian method to write a square root algorithm that is correct to within 1 ulp of the correct answer. However, I cannot figure out how to properly calculate which way the number should be rounded to represent the best possible approximation to the actual square root of the input. Answers containing principles which can be extended to other functions would be preferred, but I have heard that sqrt is a simpler case than many transcendental functions, and specialized solutions would also be much appreciated.

Also, here is a cleaned-up version of my code as of this question's original submission:

public static double sqrt(double x) {
    long bits = Double.doubleToLongBits(x);

    // NaN and non-zero negatives:
    if (Double.isNaN(x) || x < 0) return Double.NaN;

    // +-0 and 1:
    if (x == 0d || x == 1d) return x;

    // Halving the exponent to come up with a good initial guess:
    long exp = bits << 1;
    exp = (exp - 0x7fe0000000000000L >> 1) + 0x7fe0000000000000L >>> 1 & 0x7ff0000000000000L;
    double guess = Double.longBitsToDouble(bits & 0x800fffffffffffffL | exp);
    double nextUp, nextDown, guessSq, nextUpSq, nextDownSq;

    // Main loop:
    while (true) {
        guessSq = guess * guess;
        if (guessSq == x) return guess;
        nextUp = Math.nextUp(guess);
        nextUpSq = nextUp * nextUp;
        if (nextUpSq == x) return nextUp;
        if (guessSq < x && x < nextUpSq) {
            double z = x / nextUp;
            if (z * nextUp > x) z = Math.nextDown(z);
            return z < nextUp ? nextUp : guess;
        }
        nextDown = Math.nextDown(guess);
        nextDownSq = nextDown * nextDown;
        if (nextDownSq == x) return nextDown;
        if (nextDownSq < x && x < guessSq) {
            double z = x / guess;
            if (z * guess > x) z = Math.nextDown(z);
            return z < guess ? guess : nextDown;
        }

        // Babylonian method:
        guess = 0.5 * (guess + x / guess);
    }
}

As you can see, I was using division as a test. However, I believe that requires the division to round towards 0, which obviously doesn't happen in Java.

Answer 1

By the Taylor theorem, the square root function is locally approximated by a linear function, of slope 1/2√x, which is positive. So you can relate the error to the error in the square, x - (√x)², where √x is understood to be the approximate root. Then you round in the direction that minimizes this error.

Anyway, the computation of x - (√x)² is subjected to catastrophic cancellation and you may need extended accuracy to compute it reliably. Not sure the benefit is worth the effort.