Division of Large Numbers - Newton's Iteration

(Page 2 of 4 )

The technique is also known as Newton-Raphson method, and in order to fully understand this section a little math knowledge is required. However, if some parts seem tougher, you shouldn't worry at all. You still will be able to use the method, you just won't get the full picture as to why it works (after all, you can use electricity- lights, computer, TV set, fridge, et al.-without knowing how electricity truly behaves).

This is the best-known method for successfully finding a better approximation for where a real valued function will be equal to zero. The speed of the convergence can be fast, and depends very much on the starting value of the iteration. The closer to the result you start, the faster you'll get to a better result. Be warned, however, that an initial value "far" from the root will lead to an undetermined, bad result.

Briefly presented, the idea behind the method is the following: you start with an initial guess that is quite close to the root. If this is true, then its tangent line drawn in that point approximates the function. If you compute the interception between the tangent line and the initial function, the new-found intercept is typically better than the value with which you started. Now we can repeat this step until we reach a point where the value reaches an acceptable precision.

Written up in the form of math, this can be reduced to the following equation:

The convergence of this is quadratic, as the error is squared practically at each step. So while we retouch our value at each step, we extend the error rate also at a quadratic rate. So it's crucial that we get a relatively close value to the root, otherwise the iteration may fail to converge to the end result we desire.

All right, so now you may ask how this will help us in the finding of the inverse of a number. Well, what we are searching for is the root of the function f(x) = 1/x - A. We derive the function and put it into the upper equation, and we'll get x_n+1 = 2x_n-Ax_n². This involves three large number multiplications, one with a small number and a subtraction.

We can further optimize this to the form of: x_n+1 = X_n (2-Ax_n). This contains only two large number multiplications and a subtraction from 2. As for the starting value, we can go as far as five digits, as we can find out easily from using the internal division found inside every compiler/computer.

Next: The Code Snippet >>
 

More Development Cycles Articles
More By Gabor Bernat

Comments On: Division of Large Numbers

>>> Be the FIRST to comment on this article!