Post Reply 
(12C) Square Root
09-28-2020, 07:14 PM
Post: #5
RE: (12C) Square Root
(10-02-2019 02:36 PM)Albert Chan Wrote:  Ref: Numerical Analysis by Ridgway Scott, section 1.3.2, the best start

Scott's best start = (1+n) * a, where a = -8 + 6√2 ≈ 0.485281374239 was a little off.

Minimized relative errors of guess and actual root is not enough.
Taking account the effect of Newton's method, reusing previous post defined relerr()

XCas> solve(relerr(k,1) = relerr(k,2) and k > 0, k)       → \([\sqrt{\sqrt{2} / 6}]\)
XCas> a := approx(ans()[0])                                      → 0.485491771707

I tested this in lua, with added 3 Newton's iterations.
Note: Newton's iterations treated in pairs, to optimize away 1 multiply.

Code:
function fastsqrt(x)
    local g, e = frexp(x)
    if e%2 ~= 0 then g, e = g+g, e-1 end
    x = (1+g) * 0.97098 -- factor to miminize relative error
    x = x*0.25 + g/x    -- abs(1- x/g) < 4.337e-4
    x = x + g/x         -- abs(1-2x/g) < 9.400e-8
    return ldexp(x*0.25 + g/x, e*0.5)
end

Expected maximum relative error ≈ ε²/2 = (9.4e-8)²/2, ≈ 4.4e-15
And, it should occur when x is pow-of-2, or close to it.

lua> x = 1
lua> for i=1,11 do print(x, fastsqrt(x)); x=x*100 end

1         1.0000000000000044
100       10
10000     100
1e+006    1000.0000000000041
1e+008    10000
1e+010    100000
1e+012    1000000.0000000033
1e+014    1e+007
1e+016    1e+008
1e+018    1000000000.0000021
1e+020    1e+010
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)