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
 Namir Senior Member Posts: 656 Joined: Dec 2013
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
08-27-2019, 07:49 PM
Post: #2
 ijabbott Senior Member Posts: 677 Joined: Jul 2015
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
08-27-2019, 09:44 PM (This post was last modified: 08-27-2019 09:45 PM by KeithB.)
Post: #3
 KeithB Member Posts: 191 Joined: Jan 2017
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.
08-27-2019, 09:55 PM (This post was last modified: 08-28-2019 03:53 AM by Albert Chan.)
Post: #4
 Albert Chan Senior Member Posts: 696 Joined: Jul 2018
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}$$
08-28-2019, 01:39 AM
Post: #5
 Namir Senior Member Posts: 656 Joined: Dec 2013
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.
08-28-2019, 01:40 AM
Post: #6
 Namir Senior Member Posts: 656 Joined: Dec 2013
RE: Third Order Convergence for Square Roots Using Newton's Method
I corected my original post to replace A with N.
08-28-2019, 01:52 AM
Post: #7
 rprosperi Senior Member Posts: 3,576 Joined: Dec 2013
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
08-28-2019, 07:32 PM
Post: #8
 bshoring Member Posts: 258 Joined: Dec 2013
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
 « Next Oldest | Next Newest »

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