(12C) Square Root

10022019, 10:23 AM
(This post was last modified: 10032019 04:10 AM by Gamo.)
Post: #1




(12C) Square Root
For case study purpose here is the very interesting algorithm to compute the square root of a number
by using this equation. B = [A+(n÷A)] ÷ 2 This equation used Successive Approximation Algorithms that continue to better approximate some desired result by providing the initial guess then this program will converge on to the correct answer if your initial guess is bad then more iteration will be required to achieve a giving accuracy. With this program it doesn't matter where you start your initial guess because this algorithm also used the Change in the Approximation: ABS [(BA) ÷ A] and Tolerance of 0.00000001 to guarantee that the result will be possible. This equation solves for B, which is the new improved approximation for the square root of n until we are happy with this approximation, we continue repeating the process by coping the new B value into A and then reexecuting the same equation to get a new B value.  Procedure: FIX 8 n [ENTER] A [R/S] display Answer [X<>Y] number of iterations  Example: √10 used 3 as a guess 10 [ENTER] 3 [R/S] 3.16227766 [X<>Y] 3.00000000 Answer: √10 = 3.16227766 and program took 3 iterations to get this answer.  Program: Code:
Gamo 

10022019, 02:36 PM
(This post was last modified: 10192019 01:57 AM 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: 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 

10032019, 02:01 AM
(This post was last modified: 10032019 04:13 AM by Gamo.)
Post: #3




RE: (12C) Square Root
Thanks Albert Chan
Very interesting article. I have streamline this program a bit, now no counter, with an educated guess, program will take on average less than 5 iterations. This program update included Pause to observe each iterations until converge to an answer. Program: Code:
Hints: Program line 17 to 20 is the [ABS] function with this routine we avoid using n [ENTER] [x] [√x] because it is kind of funny to use [√x] in program while this program is looking for the Square Root. This [ABS] function routine is also work good on HP10C I have post earlier here https://www.hpmuseum.org/forum/thread12138.html Gamo 

« Next Oldest  Next Newest »

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