Crunching Numbers With Newton-Raphson Iteration (student warning)

http://en.wikipedia.org/wiki/Division_%28digital%29

I'm trying to divide some extremely large numbers using a Newton-Raphson iteration.

It's good because division is a linear function: (leaving out a remainder or decimal for now)

a small # eg:  987987/123
N/D = Q
987987/123 = Q
987987=123Q
f(X) = 123Q-987987
look familiar? y=mX+b

... which means that the numerator is just the Y intercept, the denominator(divisor) is the slope(delta), and the '0' of the function is the answer of the division problem.

Newton-Raphson states that with an initial guess of X(i), you gain precision by calculating X(i+1), X(i+2), .... with the following formula:

X(i+1) = X(i) - [ (f(X(i)) / delta X]
with delta X just being the denominator (slope)
eg: 987987/123 (actual answer of 8032.41463)
(guess) X(i) = 7500
iteration1 = X(i+1) = 7500 - {[123(7500) - 987987] / 123} = 6967.58537
iteration2 = x(i+1) = 6967.58537 - {[123(6967.58537) - 987987] / 123} = 8032.41463

Two iterations!

My problem is the other part of the equation, in which the reciprocal of the slope(delta or secant) of the function is solved for in order to complete the formula using only multiplication, subtraction, and addition algorithms:



for which I have substituted numbers into many different ways and can not make a reciprocal out of it. Have any fellow math/CS geeks in here dealt with this problem before?

Thanks  

The math geeks at:

http://forums.randi.org/forumdisplay.php?f=5

Would love to work on a problem like this.

Speedskater said:

The math geeks at:

http://forums.randi.org/forumdisplay.php?f=5

Would love to work on a problem like this.

Click to expand...

...Apparently they think I'm a spammer.

If you'd like to work on a problem like this, go for it... It's not that far out there.

Let's see if this gets any responses:

http://forums.randi.org/showthread.php?p=6334320#post6334320

I picked this up over at JREF, and I thought it might be helpful to drop in and post the reply here as well.

I'll stick with the example of 987987/123, but all this is perfectly general.

Firstly, using the function f(X)=123Q-987987 is both better and worse than you thought it was. Better because you mixed up a sign in your first iteration; the calculation should be:

iteration1 = X(i+1) = 7500 - {[123(7500) - 987987] / 123}
= 7500 - {[92250 - 987987] / 123}
= 7500 - { -532.41463}
= 7500 + 532.41463
= 8032.41463

For a first order polynomial, the first iteration of the Newton-Raphson approximation gives the exact answer - it's a trivial case:

X2 = X1 - {m.X1 + b} / m
= X1 - m.X1/m + b/m
= X1 - X1 + b/m
= b/m, independent of X1.

However, this also points to the reason why a first order polynomial isn't any use for speeding up the calculation; in order to calculate the correction, you need to divide by m, which is equivalent to the operation you're trying to work around. That's why the Wikipedia article suggests the alternative function f(X) = 1/X - D for determining a reciprocal. Taking a reciprocal is enough to solve your problem; here's why.

To simplify the original problem of 987987/123 to one that only involves multiplication and addition, we can take the reciprocal of 123 and multiply by 987987. To simplify it further, we can take the reciprocal of 1.23, multiply by 987987, and shift the decimal point two places to the left - or, of course, multiply by 9879.87. So, let's use your expression out of Wikipedia to determine 1/1.23. There's no substitution required; you've actually posted the answer.

X(i+1) = X(i) [ 2 - ( D * X(i) ) ]

I'll take a starting guess of 0.75, and iterate a couple of times. (Actually, a reasonably good starting guess might be 0.77, based on the first term of the polynomial expansion of 1/(1+X), but I only thought of that after I did the arithmetic.)

X(1) = 0.75
X(2) = 0.75 [ 2 - ( 0.75 * 1.23 ) ] = 0.808125
X(3) = 0.808125 [ 2 - ( 0.808125 * 1.23 ) ] = 0.8129788

From my calculator, 1/1.23 = 0.81300813... , so two guesses gets within .00003 of the correct answer, or .004%.

To get from there to the full solution:

Result = 0.8129788 * 9879.87 = 8032.124

Again, pretty close for only two iterations.


Hope this helps,

Dave

Thanks Dave, this is all way out of my ballpark.