(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
 Albert Chan Senior Member Posts: 2,566 Joined: Jul 2018
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)