Post by: SMcNeill on March 09, 2021, 04:27:30 am
Code: QB64: [Select]
- INPUT "What number do you want to find the square root of:"; n
- s = SQRT(n)
- PRINT "-----------------------------------------------------------"
- b = FindBase(n) 'first, find the base, which is the smallest whole number squared that's smaller than our actual number.
- step1 = (n / b + b) / 2 'then take the average of that value and your number divided by that value
- step2 = n / step1 'get the value of your number divided by that number, for greater precision
- SQRT = (step1 + step2) / 2 'and take the average of those two values
- FindBase = -1 'not found; value is too large
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
Post by: SMcNeill on March 09, 2021, 04:30:50 am
Code: QB64: [Select]
- INPUT "What number do you want to find the square root of:"; n
- s = SQRT(n)
- PRINT "-----------------------------------------------------------"
- b = FindBase(n) 'first, find the base, which is the smallest whole number squared that's smaller than our actual number.
- step1 = (n / b + b) / 2 'then take the average of that value and your number divided by that value
- b = n / step1 'get the value of your number divided by that number, for greater precision
- SQRT = (step1 + b) / 2 'and take the average of those two values
- FindBase = -1 'not found; value is too large
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. ;)
Post by: STxAxTIC on March 09, 2021, 11:24:52 am
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]
- 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]
- 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.
Post by: bplus on March 09, 2021, 11:30:39 am
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. ;)
Post by: STxAxTIC on March 09, 2021, 11:37:48 am
It's the Babylonian method.
Post by: bplus on March 09, 2021, 11:38:05 am
Quote
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.
Post by: STxAxTIC on March 09, 2021, 11:43:08 am
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.
Post by: bplus on March 09, 2021, 11:48:32 am
Post by: SMcNeill on March 09, 2021, 12:02:59 pm
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
Post by: bplus on March 09, 2021, 02:31:02 pm
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.