Newton Method Square Root Iterations

Question

I pulled this code from http://blog.shay.co/newtons-method/:

//a - the number to square root
//times - the number of iterations
public double Sqrt(double a, int times)
{
    if (a < 0)
        throw new Exception("Can not sqrt a negative number");
    double x = 1;
    while (times-- > 0)
        x = x / 2 + a / (2 * x);
    return x;
}

What is a good rule of thumb for the number of iterations on a number, if one exists? (For example, "Use n/2 iterations".)

Answer 1

What is a good rule of thumb for the number of iterations on a number, if one exists?

Newton's method has quadratic convergence, ie. at every step of the algorithm, the number of significant digits in the answer doubles. Thus the algorithm computes square roots upto D digits of precision in O(log D) time. Thus the number of iterations in your loop will depend upon the accuracy expected. So to have a fine grained control over the accuracy of the result, you can add a check in your code that returns the answer when the estimate is not outside the error bounds.

public double Sqrt(double a){
    if (a < 0)
        throw new Exception("Can not sqrt a negative number");
    double error = 0.00001;
    double x = 1;
    while (true){
        double val = x*x;
        if(abs(val-a) <= error)
             return x;
        x = x / 2 + a / (2 * x);
    }
}