(12C) Square Root
|
10-02-2019, 02:36 PM
(This post was last modified: 10-15-2020 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.428e-7 → 2.947e-14 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(1-k*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 - 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)