Third Order Convergence for Square Roots Using Newton's Method

[Albert Chan]

(08-27-2019 06:32 PM)Namir Wrote:  X(n+1) = X(n)*(X(n)^2 + 3*N)(3*X(n)^2 + N)

where X(0) is the initial guess for the square root of N.

I wonder if this is more efficient than applying Newton's method twice.
Assuming X(n)^2 is calculated and saved, above required 2 add, 3 mul, 1 div

Quote:X(n+1) = (X(n) + N/X(n)) / 2

Newton's (applied twice): 2 add, 2 div, 2 bit-shift (or, replace /2 by *0.5, 2 mul)
But, 2 Newton's give quartic convergence !

---

Apply Newton's mentally, division part is not easy.
Rewrite Newton's method as corrections to guess maybe easier.

X(n+1) = X(n) + (N-X(n)^2)/2 / X(n)

Apply this again, we can avoid calculating (N-X(n+1)^2) with this equivalent formula:

X(n+2) = X(n) + (N-X(n)^2)/2 / harmonic_mean(X(n), X(n+1))

Simplify away harmonic_mean(), and 2*X(n)*X(n+1) = N+X(n)^2, we get:

X(n+2) = X(n) + (N-X(n)^2)/2 * (X(n)+X(n+1)) / (N+X(n)^2)

Example, guess 7 for √51 ≈ 7.14142842854285

(N-X(0)^2)/2 = (51-49)/2 = 1

X(1) = 7 + 1/7 = 7.(142857)
X(2) = 7 + 1*(7+(7+1/7)) / (51+49) = 7 + (14+1/7) / 100 = 7.14(142857)

For comparison, Newton's formula from X(1) to X(2):

X(2)
= (7+1/7) + (51-(7+1/7)^2)/(2*(7+1/7))
= (7+1/7) + (51-(49+2+1/49)) / (100/7)
= (7+1/7) + (-1/49)*7/100
= (7+1/7) − 1/700
= 7.14(142857)