Third Order Convergence for Square Roots Using Newton's Method

08272019, 06:32 PM
(This post was last modified: 08282019 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 pseudocode for the second algorithm is: Given N and X (initial guess) and tolerance toler: Code:
Enjoy! Namir 

08272019, 07:49 PM
Post: #2




RE: Third Order Convergence for Square Roots Using Newton's Method
(08272019 06:32 PM)Namir Wrote: I stumbled on a third order converging algorithm in an book about ODEs and PDEs. The algorithm is: Quote:Given N and X (initial guess) and tolerance toler: Hi Namir, Could you clarify what variable A is used for? Thanks! — Ian Abbott 

08272019, 09:44 PM
(This post was last modified: 08272019 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.


08272019, 09:55 PM
(This post was last modified: 08282019 03:53 AM by Albert Chan.)
Post: #4




RE: Third Order Convergence for Square Roots Using Newton's Method
(08272019 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 3nbit precise answer, all 3 factors required 3nbits This may be better, correction terms requiring only 2nbits: Halley's formula for \(\Large \sqrt N: x _{new} = x  {2x(x^2N) \over 3x^2 + N}\) Example: N=12345, √N = 111.10 80555 13540 51124 ... Try 5digits decimal guess = 111.11 , √N → 111.10 80555 13540 66013 Try 16bits binary guess = 0xde37p9, √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^3N) \over 2x^3 + N}\) 

08282019, 01:39 AM
Post: #5




RE: Third Order Convergence for Square Roots Using Newton's Method
(08272019 07:49 PM)ijabbott Wrote:(08272019 06:32 PM)Namir Wrote: I stumbled on a third order converging algorithm in an book about ODEs and PDEs. The algorithm is: A is a typo .. should be N. 

08282019, 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.


08282019, 01:52 AM
Post: #7




RE: Third Order Convergence for Square Roots Using Newton's Method
(08282019 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 

08282019, 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 HP67?
Regards, Bob 

« Next Oldest  Next Newest »

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