Newton's method is amazing because each iteration (each loop) doubles the number of correct digits of the answer.

Newton's Method is used to find successive approximations to the roots of a function. If the function is y = f(x) and x₀ is close to a root, then we usually expect the formula below to give x₁ as a better approximation. Then you plug the x₁ back in as x₀ and iterate.

Here's an illustration of the method:

(click image for another illustration)

Following the link above (or here) illustrates another problem: Newton's method doesn't necessarily work well, or even work at all, unless you get to an initial guess that is close to the root.

A number of web pages explain how the above formula for Newton's method is derived. For example:

1. Newton's method (Wikipedia).
2. Newton's method.
3. Newton's method (MIT course).
4. Newton's method.

Historically, Newton's method has been used in software and in hardware for two impressive tasks: carry out division, and compute the square root. Early in the computer era addition (and subtraction, of course), along with multiplication, were implemented in hardware. Division was quite a bit harder to implement. Think about the multiplication and division by hand that you (surely) learned early in school. Programming multiplication would be relatively straightforward compared with division, which involved successively guessing the next digit to use for the quotient. To quote from Knuth (Vol. 2, page 251):

Double-precision floating division is the most difficult routine, or at least the most frightening prospect we have encountered so far in this chapter. Actually, it is not terribly complicated once we see how to do it; ...

Here are the steps in this process:

• Normalization: Start with a number x, where we want either 1/x or sqrt(x). First normalize the input to some small range using powers of 2. With binary floating point numbers, multiplication or division by a power of two only needs to adjust the exponent part of the number, which can be done very quickly.
  • For division, normalize into the interval 0.5 <= x <= 1 by multiplying by a suitable power of two. At the end, denormalize by multiplying by the same power of two (since the answer inverted the previous normalization factor).
    

  • For square root, normalize into the interval 0.25 <= x <= 1 by multiplying by an even power of two. At the end, denormalize by dividing by the square root of the normalizing factor, namely half the size of the exponent.
    

• Initial Approximation: Use a simple approximating function, as illustrated for the general division and square root routines presented below, to get a good initial guess at the answer.

• Final Calculation: Starting from the initial guess of the previous step, use Newton's method to converge to the answer.

Square Root of Two. Here there is no normalization, and only a specific square root. It would not be hard to add normalization and square roots of arbitrary numbers.

This page shows the rapid convergence of Newton's method. In this case, 9 loop iterations yield 391 decimal digits of the answer.

Square Root. The square root of an arbitrary double r > 0 using normalization as explained above.

Division. The reciprocal of an arbitrary positive double d > 0 using normalization.

Square Root Compared with Division. This page shows the remarkable similarity between the code for division and that for square root.