Post Reply 
(12C) Square Root
09-28-2020, 05:18 PM
Post: #4
RE: (12C) Square Root
(10-02-2019 02:36 PM)Albert Chan Wrote:  guess = 0.365 * (1 + n) reduced max_rel_err to 27%, thus required at most 4 iterations.

Turns out above is not the optimal. It should be guess = 0.37913 * (1+n), 0.1 ≤ n ≤ 10

For increasing function, Newton's method preferred a guess on the right.
I learned about this from "Fast Inverse Square Root", by Chris Lomon

One application of Newton's method automatically gives a guess, to the right of actual root.
Example, sqrt(n = 0.7) ≈ 0.83666

x = 0.37913*(1+n) ≈ 0.64452 (guess to the left of root)
x = (x + n/x) / 2     ≈ 0.86530 (guess, now to the right)

XCas> nt(x,n) := (x + n/x)/2
XCas> relerr(k,n) := 1 - nt(k*(1+n),n) / sqrt(n)        // note: relative error ≤ 0
XCas> solve(relerr(k,1) = relerr(k,10) and k>0, k)    → \([\sqrt{\sqrt{10} / 22}]\)
XCas> k0 := approx(ans()[0])                                 → 0.379130444101

Relative error (worst case) at n=0.1, or 1., or 10.
With guess = k0*(1+n), how many iterations to ensure full convergence ? Try n=1 (note: √1=1)

XCas> nt(k0*2, 1)       → 1.03853409762
XCas> nt(ans(), 1)       → 1.00071489067
XCas> nt(ans(), 1)       → 1.00000025535
XCas> nt(ans(), 1)       → 1.0

4 Newton iterations will converged to full 12 digits

P.S. above shows Newton's method on square-root, convergence rate ≈ ε²/2
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
(12C) Square Root - Gamo - 10-02-2019, 10:23 AM
RE: (12C) Square Root - Albert Chan - 10-02-2019, 02:36 PM
RE: (12C) Square Root - Albert Chan - 09-28-2020 05:18 PM
RE: (12C) Square Root - Albert Chan - 09-28-2020, 07:14 PM
RE: (12C) Square Root - Gamo - 10-03-2019, 02:01 AM
RE: (12C) Square Root - SlideRule - 09-28-2020, 09:45 PM
RE: (12C) Square Root - Albert Chan - 06-08-2021, 03:36 PM
RE: (12C) Square Root - depor - 12-21-2023, 11:50 PM
RE: (12C) Square Root - Dave Hicks - 12-23-2023, 01:48 AM
RE: (12C) Square Root - Thomas Klemm - 12-23-2023, 04:26 AM



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