Averaging method of finding square roots

[SMcNeill]

Code: QB64: [Select]

1. CONST Limit = 10000
2. DIM SHARED Squares(Limit) AS LONG: FOR i = 0 TO Limit: Squares(i) = i * i: NEXT
3. DO
4.     INPUT "What number do you want to find the square root of:"; n
5.     IF n = 0 THEN EXIT DO
6.     s = SQRT(n)
7.     PRINT USING "My quess is ######.######, which squared becomes ######.######"; s; s * s
8.     PRINT USING "The actual value is ######.######, which squared becomes ######.######"; SQR(n); SQR(n) * SQR(n)
9.     PRINT "-----------------------------------------------------------"
10. LOOP
11. CLS
12. FOR i = 1 TO 20
13.     PRINT i, SQRT(i), SQRT(i) * SQRT(i)
14. NEXT
15.  
16.  
17.  
18.  
19. FUNCTION SQRT (n)
20.     b = FindBase(n) 'first, find the base, which is the smallest whole number squared that's smaller than our actual number.
21.     step1 = (n / b + b) / 2 'then take the average of that value and your number divided by that value
22.     step2 = n / step1 'get the value of your number divided by that number, for greater precision
23.     SQRT = (step1 + step2) / 2 'and take the average of those two values
24. END FUNCTION
25.  
26. FUNCTION FindBase (num AS LONG)
27.     FOR i = 1 TO Limit
28.         IF Squares(i) > num THEN FindBase = i - 1: EXIT FUNCTION
29.     NEXT
30.     FindBase = -1 'not found; value is too large
31. END FUNCTION

So as to not keep derailing BSpinoza's topic about Heron's Method to calculate squares, I thought I'd just start a new one here for this example, which STx might want to compare against all his fancy-pancy math formulas which estimate to .1% accuracy.  All we're doing here is some basic averaging to find an estimation which is almost comparable to that .1% accuracy -- no formulas, scribbled notes, or math text books needed!  Just add two numbers together and divide by two for the average!  :P

[SMcNeill]

And for even better results, just continue to get the average a few more times.  Here's an example of 3 passes of averaging:

Code: QB64: [Select]

1. CONST Limit = 10000
2. DIM SHARED Squares(Limit) AS LONG: FOR i = 0 TO Limit: Squares(i) = i * i: NEXT
3. DO
4.     INPUT "What number do you want to find the square root of:"; n
5.     IF n = 0 THEN EXIT DO
6.     s = SQRT(n)
7.     PRINT USING "My quess is ######.######, which squared becomes ######.######"; s; s * s
8.     PRINT USING "The actual value is ######.######, which squared becomes ######.######"; SQR(n); SQR(n) * SQR(n)
9.     PRINT "-----------------------------------------------------------"
10. LOOP
11. CLS
12. FOR i = 1 TO 20
13.     PRINT i, SQRT(i), SQRT(i) * SQRT(i)
14. NEXT
15.  
16. FUNCTION SQRT (n)
17.     b = FindBase(n) 'first, find the base, which is the smallest whole number squared that's smaller than our actual number.
18.     FOR i = 1 TO 3
19.         step1 = (n / b + b) / 2 'then take the average of that value and your number divided by that value
20.         b = n / step1 'get the value of your number divided by that number, for greater precision
21.     NEXT
22.     SQRT = (step1 + b) / 2 'and take the average of those two values
23. END FUNCTION
24.  
25. FUNCTION FindBase (num AS LONG)
26.     FOR i = 1 TO Limit
27.         IF Squares(i) > num THEN FindBase = i - 1: EXIT FUNCTION
28.     NEXT
29.     FindBase = -1 'not found; value is too large
30. END FUNCTION

Note:  If you print values as _FLOAT values, you'll see that we reach the same precision as QB64's SQR command has, with only 4 averages.  If you have to have greater precision than that, you'll need to swap over to string math routines instead.  ;)

[STxAxTIC]

Alright, so the available criticisms of the entire thing are rather obvious to me, but I feel like making things clear to the audience. Don't take this too critically Steve - it's all friendly banter and you already know what I'm about to throw. Some people just need to see two different attitudes duke it out publicly. So how do I even start?

Regarding your first code box, I almost thought you COMPLETELY misunderstood what was going on, and then I noticed the 4 blank lines after the "main" part of your program, so then I scrolled down beyond the visibility of the code box, and saw the rest. I only feel like people with something to hide tend to do this on purpose - I'm sure it was an accident.

Anyway, I finally spot the nuts and bolts of this program (onto code box 2 now) - only to find a bunch of looping and temp variables. This means you cannot compare what you're doing to my "one shot" methods that do the entire estimation in one iteration. Definitely my fault for not starting my own thread on that. If you want a real apples-to-apples comparison, you need to square yourself (second box) against my ITERATIVE methods. Unfortunately the only one of those I posted here was the Babylonian method - and it turns out that is 90% what you're doing. Look at your line:

Code: QB64: [Select]

1. step1 = (n / b + b) / 2

... That IS the Babylonian method, atomically. Even if you implement it poorly, it's gonna eventually work. (This sentiment absolutely echoes what was going on at the other thread.) Next, if you want anyone to believe that

Code: QB64: [Select]

1. b = n / step1

is the best next thing to do, you'll need to explain your reasoning properly. This might entail writing those dreaded "scribbled notes" though.

Properly detailing your work is a cultural obligation. Why? Almost nothing within reach in the world is undiscovered. Every trick and technique has been already been named. Most attempts to find something new are mere rediscoveries of something already known. (Sometimes you realize this with pleasure, other times in anger.) The point is, we always try to match our discoveries onto the existing world, i.e. "here is Heron's method", "here is what the Babylonians did", or "this is Newton's method". If you Wiki this very topic you'll get enough responses and techniques to fill many books.

What I'm saying is "Steve's Method" might not exist, and until we know what's going on with it, should only be regarded as a pale implementation of what is already known. It's up to the author to either (i) find the pre-existing idea it resembles and duly assign credit, or (ii) write up your work nicely if it's suspected to be novel. Good ideas should not just be "trapped" in code.

I know, I know, here it comes:

"But it works for me and my needs and I'm going to be lazy about points (i) and (ii)." Fine, but this the attitude is of astrologers and alchemists.

[bplus]

PS STx posted while I was composing the following, do we find the same to criticize?

LOL!

Yeah I don't see the reason for all that math just for a guesstimate, unless the guess can be refined to any limit (but then calculus could claim it in spirit at least).

Sure maybe a low amount of passes for averaging part but you aren't counting ALL the passes to find the integer whose square is just below the number in question and the next integer (squared) is above.  That's 32 tests for N = 1000 versus 1 making the first guess 1/2 of N for Heron, BSpinoza and yours truly.

Also I don't think this method would work well for say 1/2? Maybe for rational numbers find the sqr for numerator and then for denominator and then do the dividing?

Steve's magic here is a slight of hand trick. ;)

[STxAxTIC]

Okay I couldn't resist and did option (i) on Steve's behalf.

It's the Babylonian method.

 

 

[bplus]

Yeah I don't see the reason for all that math just for a guesstimate, unless the guess can be refined to any limit (but then calculus could claim it in spirit at least).

Yeah so Heron was doing calculus in spirit and Archimedes was king of doing it in spirit.

[STxAxTIC]

Yeah so Heron was doing calculus in spirit and Archimedes was king of doing it in spirit.

Not to nerd out too hard, but it depends on the definition of "calculus". If we mean taking small limits, then - well, I guess these guys knew about limits but not anything else... But if any of them regarded their work as "fancy division by zero", as Newton did, then I would call it calculus in the classic sense. Otherwise it's just limits.

[bplus]

Yeah and I say Archimedes was one giants shoulder Newton was standing on.

[SMcNeill]

PS STx posted while I was composing the following, do we find the same to criticize?

LOL!

Yeah I don't see the reason for all that math just for a guesstimate, unless the guess can be refined to any limit (but then calculus could claim it in spirit at least).

Sure maybe a low amount of passes for averaging part but you aren't counting ALL the passes to find the integer whose square is just below the number in question and the next integer (squared) is above.  That's 32 tests for N = 1000 versus 1 making the first guess 1/2 of N for Heron, BSpinoza and yours truly.

You’re dealing with 32 tests simply because I checked my array from 0 to ubound.  You can reduce that number considerably by using a simple binary comparison routine.  (A 3 or 4 digit number must have a 2 digit root, giving only 7 binary comparisons to check all the possibilities.)

A linked list (as STx likes to extoll the value of constantly) could find your base with a single lookup...

But you’re right — it’s all honestly slight of hand.  At the end of the day, we’re still taking averages in a loop to zoom in to the base, just like with Heron’s method.  (Which is why I posted the second post to help illustrate that.)  The first post just goes to show that if we know the base, we can get an extremely close estimation with just a single, simple set of averages.

I broke the math down to 3 simple steps, but we could have done this instead:

SQRT = ((n / b + b) /2) + (n / (n / b + b) / 2 )) /2

Now *that* would’ve really been trying to hide the smoke and mirrors in the magic show!  ;D

[bplus]

Yeah, you know doing it in one shot is a nice goal too, I've been thinking about that, yeah nice and mathy!!! LOL

It might be one shot calculation but there is a hell of allot more thinking involved in getting a really good guess and knowing it's going to work for any number.