(12C) Square Root
09-28-2020, 07:14 PM
Post: #5
 Albert Chan Senior Member Posts: 2,565 Joined: Jul 2018
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
 « Next Oldest | Next Newest »

 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)