How to show this formula to get a square root of a number in "just few seconds" is true?

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

\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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.