Post Reply 
Third Order Convergence for Square Roots Using Newton's Method
08-27-2019, 06:32 PM (This post was last modified: 08-28-2019 01:41 AM by Namir.)
Post: #1
Third Order Convergence for Square Roots Using Newton's Method
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
Find all posts by this user
Quote this message in a reply
08-27-2019, 07:49 PM
Post: #2
RE: Third Order Convergence for Square Roots Using Newton's Method
(08-27-2019 06:32 PM)Namir Wrote:  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 + A)
where X(0) is the initial guess for the square root of N.
Quote:Given N and X (initial guess) and tolerance toler:

Code:

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

Hi Namir,

Could you clarify what variable A is used for? Thanks!

— Ian Abbott
Find all posts by this user
Quote this message in a reply
08-27-2019, 09:44 PM (This post was last modified: 08-27-2019 09:45 PM by KeithB.)
Post: #3
RE: Third Order Convergence for Square Roots Using Newton's Method
It looks to be the root you are looking for, since you are comparing it to the guess * the guess.
Find all posts by this user
Quote this message in a reply
08-27-2019, 09:55 PM (This post was last modified: 08-28-2019 03:53 AM by Albert Chan.)
Post: #4
RE: Third Order Convergence for Square Roots Using Newton's Method
(08-27-2019 06:32 PM)Namir Wrote:  X(n+1) = X(n)*(X(n)^2 + 3*N)/(3*X(n)^2 + N)

Hi, ijabbott. Typo fixed

However, this setup may not be ideal for arbitrary precision math.
For a 3n-bit precise answer, all 3 factors required 3n-bits

This may be better, correction terms requiring only 2n-bits:

Halley's formula for \(\Large \sqrt N: x _{new} = x - {2x(x^2-N) \over 3x^2 + N}\)

Example: N=12345, √N = 111.10 80555 13540 51124 ...

Try 5-digits decimal guess = 111.11 ,   √N → 111.10 80555 13540 66013
Try 16-bits binary guess = 0xde37p-9, √N → 111.10 80555 13540 50609

You can DIY other functions, see Method of obtaining Third Order Iterative Formulas

Example: Halley's formula for \(\Large \sqrt[3] N: x _{new} = x - {x(x^3-N) \over 2x^3 + N}\)
Find all posts by this user
Quote this message in a reply
08-28-2019, 01:39 AM
Post: #5
RE: Third Order Convergence for Square Roots Using Newton's Method
(08-27-2019 07:49 PM)ijabbott Wrote:  
(08-27-2019 06:32 PM)Namir Wrote:  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 + A)
where X(0) is the initial guess for the square root of N.
Quote:Given N and X (initial guess) and tolerance toler:

Code:

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

Hi Namir,

Could you clarify what variable A is used for? Thanks!

A is a typo .. should be N.
Find all posts by this user
Quote this message in a reply
08-28-2019, 01:40 AM
Post: #6
RE: Third Order Convergence for Square Roots Using Newton's Method
I corected my original post to replace A with N.
Find all posts by this user
Quote this message in a reply
08-28-2019, 01:52 AM
Post: #7
RE: Third Order Convergence for Square Roots Using Newton's Method
(08-28-2019 01:40 AM)Namir Wrote:  I corected my original post to replace A with N.

Albert's typo comments also inserted a division symbol in the middle. Does that belong there as well?

Also, does anyone know what the ":x" symbology means in front of the equations Albert proposed?

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
08-28-2019, 07:32 PM
Post: #8
RE: Third Order Convergence for Square Roots Using Newton's Method
Could we have an example of this in RPN, say for HP-67?


Regards,
Bob
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)