Third Order Convergence for Square Roots Using Newton's Method

[Namir]

Hi All,

Most of us are familiar with the second order converging algorithm for obtaining the square root of N:

X(n+1) = (X(n) + N/X(n)) / 2
where X(0) is the initial guess for the square root of N.

I stumbled on a third order converging algorithm in an book about ODEs and PDEs. The algorithm is:


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 compared the two algorithms using Excel and the second one does converge faster than the first one.

The pseudo-code for the second algorithm is:

Given N and X (initial guess) and tolerance toler:

Code:


Repeat
  Y = X*X;
  X = X * (Y + 3*N) / (3*Y + N)
Until Abs(X*X-N) <= toler

Enjoy!

Namir