1
$\begingroup$

this is my first post here and I wanted to run something by people who are more knowledgeable than I. In the past couple days I've decided that I need to teach myself more advanced mathematics as it is of great importance to my studies in physics, astronomy and biology. In school we never went past algebra 1 and geometry and that has proven to be a hindrance. So I decided to brush up on the basic math that I learned in school and then move on to more advanced maths. I decided to make up a bunch of problems to solve while waiting for my books to arrive and I ran into my old nemesis, finding square roots of large numbers. I was taught prime factorization, which didn't work for this number, and the Babylonian Method, which can yield accurate results depending on the accuracy of your initial estimate and how many times you're willing to run the equation. What I wanted was an equation that used simple math and a known number instead of an assumed estimate (that must be high in the case of the Babylonian Method) that didn't have to be high or low that would yield an equally/greater accurate estimate of the square as does the BM, and would only have to be run once. I realize this is simple mathematics compared to what is normally discussed here, so I apologize, and also please forgive me if my terminology isn't quite correct. What I came up with was

√S≈((S/2)/(e/2)+e)/2

in this S is the number we are trying to find the square of and e is the closest perfect square root regardless of weather it is high or low.

For example, using 1,863 the number I was initially trying to find the square of, we know that the closest perfect square root is 43. So it would look like this

√1,863≈((1863/2)/(43/2)+43)/2

√1,863≈((931.5)/(21.5)+43)/2

√1,863≈(43.325+43)/2

√1,863≈ 86.325/2

√1,863≈ 43.163

Actual square of 1863=43.1624

so the estimate it yielded was very close. I've run a bunch of numbers through it both large and small and so far it appears to give better estimates than the BM (depending on the accuracy of your initial high estimate and number of times you run it through the equation) and without the requirement that the estimate is high, and also we don't have to make an initial estimate ourselves as the starting estimate is fixed for us by the nature of the equation.

What do you guys think? Is there something I've missed or perhaps is there an easier equation like it that I am not familiar with?

Thanks!

$\endgroup$
  • $\begingroup$ Does the question have more to do with an iterative programming solution? Heron's method for example. You ask would only have to be run once but I don't believe there is such a method. $\endgroup$ – Weather Vane Aug 25 '17 at 19:25
  • $\begingroup$ ... any more than there is a one-off method of factorising, of which the square root is a special case. $\endgroup$ – Weather Vane Aug 25 '17 at 19:31
  • $\begingroup$ I don't get the question. You are solving the square root of $1,863$ with the nearest known square root $43$? Tautology. You can use a convergent solution with almost any seed value. $\endgroup$ – Weather Vane Aug 25 '17 at 19:36
  • $\begingroup$ What I intended by only run once is that in the Babylonian Method the estimate has to be distilled though it several times in order to reach a acceptable level of accuracy. What I wanted was an equation that would take but one run through to supply me with an estimate of acceptable accuracy. If I ran this number through the Babylonian Method, using 44 as the high estimate the sqaure of the provided number is off by about .6 which to me it too much. With this it's off by only .0001, and that seems to also be the case with the numbers I've run through it thus far. What I'm asking really... $\endgroup$ – Craiger1987 Aug 25 '17 at 19:42
  • $\begingroup$ ... is do you believe what I've come up with is a good solution to use for finding accurate square root estimates, or is there perhaps an easier method of comparable accuracy that I'm not yet familiar with. $\endgroup$ – Craiger1987 Aug 25 '17 at 19:44
0
$\begingroup$

The relation $\sqrt S\approx\dfrac{1}{2} \left(\dfrac{\frac{S}{2}}{\frac{ e}{2}}+e\right)$ can be simplified to

$\sqrt S\approx\dfrac{1}{2} \left(\dfrac{S}{e}+e\right) $

if you square both sides you get (trust me)

$S\approx\dfrac{1}{4} \left(\dfrac{S^2}{e^2}+e^2+2S\right)$

the right side can be written as (trust me again)

$S\approx S+ \dfrac{\left(S-e^2\right)^2}{4 e^2}$

$S$ can be cancelled from both sides and we have

$\dfrac{\left(S-e^2\right)^2}{4 e^2}\approx 0$

Numerator is very very little because we choose $e $ close to $\sqrt S$ while denominator is about $4S$ therefore the fraction is very little and the approximation works

The larger the $S$ the more accurate is the approximation

I tried $\sqrt{123456789}$ and with you formula I got $11111.1110611$

while the actual value is $11111.1110605$

The only problem is to know that the square closest to $123456789$ is $11111^2$

Hope this helps :)

$\endgroup$
  • $\begingroup$ Thanks that does help a lot :) I wish there was a like button or some such, but I do appreciate all the comments and input so far it's a great help! $\endgroup$ – Craiger1987 Aug 25 '17 at 20:26
  • 1
    $\begingroup$ @Craiger1987 there is: an accept check mark, for you to mark the best answer. $\endgroup$ – Weather Vane Aug 25 '17 at 20:32
  • $\begingroup$ The only problem is to know that the square closest to $123456789$ is $111112$. Another tautology? I have to know the answer to tell you the answer. $\endgroup$ – Weather Vane Aug 25 '17 at 20:53
  • $\begingroup$ Idk if I would say it's a tautology. It's not that you have to know the answer to tell you the answer, it's that you find the closest approximation, using simple multiplication, to find the closest square route which can be off by as much as .5, and then running it through to achieve an estimate very close to the actual sqaure route. In this example we get as close as 43 using simple multiplication, and then find that that is off by .163 after running it. $\endgroup$ – Craiger1987 Aug 25 '17 at 21:23
  • $\begingroup$ @WeatherVane Even to use Newton method or fixed point methods you have to know what to start the iteration with. IMO the method is fine as a fun curiosity. The real flaw is that the approximation ends with a fixed number and can't converge to the actual value with an arbitrary degree of precision $\endgroup$ – Raffaele Aug 25 '17 at 21:56
-1
$\begingroup$

If you allow yourself to use a table of square roots, the best method is to lookup the closest entry in the table and start the Babylonian method from there. It is hards to beat that (I mean in terms of choosing an initial guess).

But what you describe is strictly the Babylonian method, nothing new. Note that it is wrong that the initial estimate must be by excess.

$\endgroup$
  • 1
    $\begingroup$ If you have a table of square roots, wouldn't it be faster to first interpolate from the two bracketing table values? $\endgroup$ – Weather Vane Aug 25 '17 at 20:06
  • $\begingroup$ @WeatherVane: that needs to be investigated. Because interpolation has itself a cost, and may give a poorer approximation than the first iteration of Newton alone. The answer probably depends on the accuracy of the table. This is an interesting question. $\endgroup$ – Yves Daoust Aug 25 '17 at 20:09
  • $\begingroup$ @WeatherVane: on second thoughts, you must be right. Linear interpolation bewtween the bracketing values corresponds to a chord of the curve. While a single Newtonian iteration from the closest value correspond to two portions of the tangents at the bracketing points (each on the half interval), and will probably be a worse approximation. And the linear interpolation can be fast if you take care to precompute the slopes (or even a best fit line in the minmax sense - or parabola). $\endgroup$ – Yves Daoust Aug 25 '17 at 20:24
  • 1
    $\begingroup$ @WeatherVane: your tone is strange, I am not fighting for anything and I don't recall that you asked anything. I would also prefer to avoid tables, but this depends on context. $\endgroup$ – Yves Daoust Aug 25 '17 at 20:53
  • 1
    $\begingroup$ @WeatherVane: no, I was talking to the OP who is using such a table. That's not my recommendation. But it would be foolish to refuse them in any situation. $\endgroup$ – Yves Daoust Aug 25 '17 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.