(12C) Square Root

10022019, 02:36 PM
(This post was last modified: 10152020 11:45 PM by Albert Chan.)
Post: #2




RE: (12C) Square Root
It might be better not asking the user to supply a possibly bad guess.
Instead, user is limited to enter value between 0.1 to 10 For example, N=12345, user entered n=1.2345, √N = 100 √n A naive guess = 0.5*(1+n) might create big relative errors. Worst case at the edge, n=0.1 or 10 max_rel_err = 1  0.5*11/√10 ≈ 0.7393 ≈ 74% Each iteration reduce max_rel_err to around ½(prev_rel_err)², we got: Ref: http://www.azillionmonkeys.com/qed/sqroot.html 0.7393 → 0.2732 → 0.03733 → 0.0006968 → 2.428e7 → 2.947e14 Thus, a maximum of 5 iterations to reach 10 digits accuracy. A better guess = k * (1+n), such that rel_err(n=1) =  rel_err(n=10). In other words, rel_error for n = 0.1 to 10 have 3 peaks, with W shape. XCas> simplify(solve(1k*2/1 = k*11/sqrt(10)  1, k)) → k = (22√10  40)/81 ≈ 0.365 guess = 0.365 * (1 + n) reduced max_rel_err to 27%, thus required at most 4 iterations. Ref: Numerical Analysis by Ridgway Scott, section 1.3.2, the best start 

« Next Oldest  Next Newest »

Messages In This Thread 
(12C) Square Root  Gamo  10022019, 10:23 AM
RE: (12C) Square Root  Albert Chan  10022019 02:36 PM
RE: (12C) Square Root  Albert Chan  09282020, 05:18 PM
RE: (12C) Square Root  Albert Chan  09282020, 07:14 PM
RE: (12C) Square Root  Gamo  10032019, 02:01 AM
RE: (12C) Square Root  SlideRule  09282020, 09:45 PM
RE: (12C) Square Root  Albert Chan  06082021, 03:36 PM
RE: (12C) Square Root  depor  12212023, 11:50 PM
RE: (12C) Square Root  Dave Hicks  12232023, 01:48 AM
RE: (12C) Square Root  Thomas Klemm  12232023, 04:26 AM

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