21
$\begingroup$

I don't remember in which topic I found it but I know it was there. And I still have not find a proof of this nice approximation.

Let $x$ be a non perfect square number. If $y$ is the closer perfect square to $x$ such that $y < x$ then

$$\sqrt{x}\approx \sqrt{y}+\frac{x-y}{2\cdot \sqrt{y}}$$ And it gives at the maximum two correct decimals after the decimal point.

My first reaction to try to find from where this formula goes, was to expand it, I found $$2\sqrt{xy}\approx y +\sqrt{2y}\cdot(x-y)$$ and I tried to find a remarkable identity but I failed and I'm still stuck there. Also I don't know how should I prove the maximum of two correct digits after the comma.

If we look for example to the sqare root time of $1000$, $961$ is the closer perfect square which verifies the condition. Then we have $\sqrt{1000} \approx 31 + \frac{39}{2*31} = 31.62903...$ and with a calculator we have $\sqrt{1000} = 31.6227766017...$ which is quite good.

Any hints would be appreciate, thank you in advance.

$\endgroup$
  • 12
    $\begingroup$ It's just the first order approximation of $f(x)=\sqrt{x}$. $\endgroup$ – Hmm. Jun 23 '16 at 17:00
  • 2
    $\begingroup$ Any number of calculus texts deal with the topic of linear approximation and you will find that you have the linearization of the square-root function near the value $ \ y \ $ . The denominator in the second term of your first equation comes from the derivative of $ \ y^{1/2} \ $ . $\endgroup$ – colormegone Jun 23 '16 at 17:07
  • 7
    $\begingroup$ Are you sure that you mean that it has a maximum, rather than a minimum, of two correct decimal digits? For example, applying the algorithm with $x = 962$ and $y = 961$ gives the approximation 31.016 (to 3 decimal places), which is correct (to 3 decimal places). In fact, in this case we get 5 decimal places of accuracy. $\endgroup$ – LSpice Jun 23 '16 at 19:43
  • $\begingroup$ @LSpice I am just asking how I should prove it. But I am not saying it is true. I said I found that on this website but my english is not very good so I may understood something wrong. Now you show me this counter-example I know that is false :-) $\endgroup$ – Hexacoordinate-C Jun 23 '16 at 20:01
  • 4
    $\begingroup$ @LSpice - It's certainly not a minimum, either. Consider $\sqrt{3.999999}$. This algorithm suggests 2.4999995 as a good approximation. That's good to zero places after the decimal point. (It's not even good before the decimal point.) If we restrict ourselves to integers, the algorithm suggests that $\sqrt3$ is approximately 2. On the other hand, in the case of 10004568, the error is quite small, and vanishes as $y\to\infty$. $\endgroup$ – David Hammen Jun 24 '16 at 14:44
47
$\begingroup$

To understand why this is a good approximation note that $(\sqrt{x})' = \frac{1}{2\sqrt{x}}$.

So the formula is of the form $f(x) = f(y) + f'(y)(x-y)$. See Taylor's theorem for more details.

$\endgroup$
  • $\begingroup$ Hmm thanks. It was simple in fact ! Have you got any ideas for the two digits after the comma? $\endgroup$ – Hexacoordinate-C Jun 23 '16 at 17:18
  • 7
    $\begingroup$ I am not convinced about the two digits. Take $2$ and $1$. You get $1.5$ as approximation of $\sqrt{2}$. What is true is that if one iterates the process then the number of correct digits roughly double with each additional step. $\endgroup$ – quid Jun 23 '16 at 17:26
  • $\begingroup$ @quid "it gives at the maximum two correct decimals", so having worse precision is expected. $\endgroup$ – Keen Jun 24 '16 at 0:16
  • 1
    $\begingroup$ @quid Yes, arbitrary precision should be possible given large enough arguments. $\endgroup$ – Keen Jun 24 '16 at 0:42
  • 1
    $\begingroup$ That takes me back to first year principles. Math is beautiful. $\endgroup$ – DevNull Jun 24 '16 at 17:52
41
$\begingroup$

For a purely algebraic and non-calculus derivation, use the fact that

$$x - y \; = \; (\sqrt{x} + \sqrt{y})(\sqrt{x} - \sqrt{y}),$$

then replace $\;\sqrt{x} + \sqrt{y}\;$ with $\;\sqrt{y} + \sqrt{y} = 2\sqrt{y}\;$ (since we are assuming $\sqrt{x}$ is approximately equal to $\sqrt{y})$ to obtain the approximation

$$x - y \; \approx \; 2\sqrt{y} \left( \sqrt{x} - \sqrt{y} \right).$$

Now solve for $\sqrt{x}$ by dividing both sides by $2\sqrt{y}$ and adding $\sqrt{y}$ to both sides.

$\endgroup$
  • $\begingroup$ Nice derivation. $\endgroup$ – HelloGoodbye Jun 24 '16 at 11:38
18
$\begingroup$

As presented there that would be "Newton's method." But it is older than Newton. It really is "the Babylonian" method.

The Babylonian method:

If you are looking for $\sqrt n$, take a guess and pulg it into:

$x_{k+1} = \frac 12 (x + \frac n{x_k})$

If you guess is close is close to $\sqrt{n}, \frac n{x_k}$ will will also nearly equal $\sqrt n$, but with the error on the other side of your target. Taking the mid-point is nearly on target.

This formula is algebraically equivalent to the one in your post.

Or:

If you know that $a$ is close to $\sqrt n$, and you want to give $a$ a small nudge ($x$).

$n = (a + x)^2 = a^2 + 2ax + x^2$

Since $x$ is small $x^2$ is very small, and we drop it.

$x = \frac {n-a^2}{2a}$

and finally Newton's method:

If you want to find the zero of any function. Then find a point on the curve $(x,f(x))$, draw a line tangent to the curve, through that point until it intersects the x-axis. That point $x_{n+1}$

$x_{k+1} = x_n - \frac {f(x_k)}{f'(x_k)}$

and in this case: $f(x) = x^2 - 2$

A note of caution, Newton's method runs into problems if $f'(x_k)$ is near zero.

One more derivation:

if $n = a^2 + x$ then we do a binomial expansion on $(a^2+x)^{\frac12}$

$(a^2+x)^{\frac12} = a + \frac12 a^{-1} x - \frac 18 a^{-3} x^2... $

Using just the first two terms, we once again have an equivalent formula.

$\endgroup$
8
$\begingroup$

\begin{align} \sqrt{x} &= \sqrt{y + x - y}\\ &= \sqrt{y}{\left(1 + \frac{x-y}{y}\right)}^{1/2}\\ &\approx \sqrt{y}\left(1 + \frac{x-y}{2 y}\right)\\ &= \sqrt{y} + \frac{x-y}{2 \sqrt{y}} \end{align} In going from the second to the third line above, I have used the Taylor series $\sqrt{1 + z} = 1 + \frac{z}{2} + O\left(z^2\right)$.

In fact this method is a good way of approximating square roots in mental arithmetic.

$\endgroup$
5
$\begingroup$

We may as well suppose that $y_0^2 < x < (y_0+1)^2$ for some integer $y_0$. It isn't that hard to show that $y_0 < \sqrt x < \dfrac {x}{y_0} < y_0+1$. So we can replace $\sqrt x \in (y_0, y_0+1)$ with $\sqrt x \in \left(y_0, \dfrac {x}{y_0} \right)$. Which is a smaller interval. Your algorithm chooses the next approximation, $y_1$, to be the midpoint of that interval, $y_1 = \dfrac 12 \left( y_0 +\dfrac {x}{y_0} \right) = y_0 - \dfrac 12 \left( y_0 -\dfrac {x}{y_0} \right) = y_0 - \dfrac{y_0^2 - x}{2y_0}$

Define $y_{n+1} = \dfrac 12 \left( y_n +\dfrac {x}{y_n} \right) = y_n - \dfrac{y_n^2 - x}{2y_n}$

It can be shown that $y_0 < y_2 < y_4 \cdots < \sqrt x < \cdots < y_5 < y_3 < y_1$ and that $\displaystyle \lim_{n \to \infty}y_n = \sqrt x$.

Your question is about how fast the sequence $\{ y_n \}_{n=0}^\infty$ converges to $\sqrt x$. In particular, we find that

\begin{align} \dfrac{|y_{n+1} - \sqrt x|}{|y_n - \sqrt x|^2} &= \dfrac {\left|\dfrac 12\left(y_n+\dfrac{x}{y_n}\right)-\sqrt x \right|} {|y_n - \sqrt x|^2}\\ &= \dfrac {|y_n^2 + x- 2y_n\sqrt x|} {2y_n|y_n^2 - 2y_n\sqrt x + x|}\\ &= \dfrac{1}{2y_n} \end{align}

Which we can interpret as $|y_{n+1} - \sqrt x| \approx \dfrac{1}{2\sqrt x} |y_n - \sqrt x|^2$

So if the error of the $n^{th}$ approximation is on the order of $10^{-m}$, then the error of the $(n+1)^{th}$ approximation will be on the order of $10^{-2m}$. In practical terms, the number of correct digits (approximately) doubles. This statement seems to be true for all $x >> 1$.

$\endgroup$
  • $\begingroup$ Interesting, I keep it on mind. In fact I'm a student in chemistry but I really like maths too, I am more interest by the reasoning than the result in general. And mathematics never lie, that's pretty good. Thank you for your answer. $\endgroup$ – Hexacoordinate-C Jun 23 '16 at 20:10
1
$\begingroup$

In your algorithm, replace $\sqrt{y}$ with $g$, for "guess". Then you have,

$\sqrt{x}$ is roughly $g + \frac{x-g^2}{2g}$.

The closer your guess, the better your refinement of that guess, so...

For something really amazing, once you get your $\sqrt{x}$ to two decimal places, let a new g be that value, repeat the process, and you get $\sqrt{x}$ to FOUR decimal places. In fact, you double the precision each time.

Example: $\sqrt{10}$, with $g_1 = 3$. That leads to $g_2 = 3+ \frac{10-9}{6} = 3.166666$. Not bad, good to two decimal places. Then, $g_3 = 3.166666 + \frac{10-10.277777}{6.33333} = 3.162281...$, off by less than the amount claimed above. Correct answer is $3.162278$ (rounded to six places).

The nice thing about this is that it is fault tolerant. You only need to carry half the digits desired for the next iteration. If you make a terrible mistake somewhere, it is obvious because some of the previously calculated digits will change. No problem, just repeat the procedure a couple more times and the error will cancel itself out. Yes, four-banger calculators are good for somethings. But it is still nice to have a square root button.

And you can generalize this idea to calculate the inverse of many different functions, not just the square function. See the many excellent answers above for better understanding.

$\endgroup$
-1
$\begingroup$

To find the square root of $x$ start with a guess of $y$, then evaluate an updated value of $y$ using $(y+(x/y)) /2$. Repeat as many times as desired to get a more accurate answer to more decimal places. You may start with any value of $y$. Even 1 000 000 works.

$\endgroup$
  • $\begingroup$ This answer does not address the question asked. The OP is not looking for some method of estimating square roots. Instead the poster is wanting an explanation of why the method shown works. $\endgroup$ – Paul Sinclair Jun 24 '16 at 17:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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