17
$\begingroup$

I've already received a lot of help with this problem (thank you all), and I've written up an answer with all of the information I've got in it as to why these approximations are so good.

My question is why the following rational function is such a good approximation for the square root of $x$?

$$\sqrt{x}\approx\frac{256+1792x+1120 x^{2}+112 x^{3}+x^{4}}{1024+1792x+448 x^{2}+16 x^{3}}$$

The following image illustrates that for $3\leqslant x\leqslant 7$ the two curves are almost identical:

Image

More generally why does the following formula hold with such accuracy?:

$$\sqrt{n}\approx\frac{m^{8}+28 m^{6}n+70 m^{4}n^{2}+28 m^{2}n^{3}+n^{4}}{8 m^{7}+56 m^{5}n+56m^{3}n^{2}+8m n^{3}}$$

for any real number (not just integer) $n\geqslant 1$ and:

$$m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$$

The following graph shows that for $0\leqslant n\leqslant10000$ the two curves cannot be separated by eye:

Image

And this is the logarithm of the error in that approximation which decreases cyclically (presumably due to the floor in the definition of $m$) but then starts to become slightly less accurate stepwise as $n$ increases:

Image

(Edit: Several people have mentioned Pade approximants below and that the first formula is a Pade approximant, which explains why it is such a good approximation. I would really especially like to know why the second formula is such a good approximation on the wide range I have shown in the second graph (is it related to Pade approximants also?), and I would really love to know why the process I outline in the section below of how I got these functions gives Pade approximants at all from ratios of binomial coefficients. At first glance, it seems as if there might be something deep going on here?)


How I found these and what I already know:

While messing around with maths once I noticed that $(3+\sqrt{8})^{8}\approx1331714$ with very good accuracy. Since the binomial theorem gives that $(3+\sqrt{8})^{8}=665857+235416\sqrt{8}$ and since $1331714=2\times665857$ I saw that that gave the approximation:

$$\sqrt{8}\approx\frac{665857}{235416}$$

which is quite accurate. I found this intriguing, but exploring further I found that similar near integer results were produced by:

$$(1+\sqrt{2})^{8}\approx1154$$

$$(2+\sqrt{3})^{8}\approx37634$$

$$(2+\sqrt{4})^{8}=65536$$

$$(2+\sqrt{5})^{8}\approx103682$$

$$(2+\sqrt{6})^{8}\approx153632$$

$$(3+\sqrt{7})^{8}\approx1032224$$

and so on, and I found that in general I could get a very accurate near integer from any (at least small) expression of the form $(m+\sqrt{n})^{8}$ where as $n$ increased over the integers $m$ increased as:

$$m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$$

When these expressions were expanded out they were all in the form $a+b\sqrt{n}\approx2a$ where:

$$a=m^{8}+28 m^{6}n+70 m^{4}n^{2}+28 m^{2}n^{3}+n^{4}$$

$$b=8 m^{7}+56 m^{5}n+56m^{3}n^{2}+8m n^{3}$$

From this you get my original equations that I posted.

Now there is nothing particularly interesting about the eighth powers I have been working with; ninth powers work as well (slightly more accurately) and seventh powers are slightly less accurate, giving a similar formula:

$$\sqrt{n}\approx\frac{m^{7}+21 m^{5}n+35 m^{3} n^{2}+7m n^{3}}{7 m^{6}n+35 m^{4} n^{2}+21 m^{2} n^{3}+n^{4}}$$

Thus some of the reason behind these formulae must be the fact that the $m+\sqrt{n}$ have powers tending to integers, and just about the only thing I have been able to find out about why this might work is that some of these numbers are Pisot-Vijayaraghavan numbers (i.e. their powers tend towards integers).

However, this does not explain the phenomenon, since I do not know why the effect would be greatest for $m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$ or importantly why the convergence should be of the form $(m+\sqrt{n})^{c}=a+b\sqrt{n}\approx 2a$ (which is where the approximation comes from) or why the formula derived should also hold for non-integral $n$. Rather the important part seems to lie in the formulation as:

$$\left(\frac{Even Binomial Terms}{Odd Binomial Terms}\right)^{\pm 1}$$

and perhaps in the expression $m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$.

So my question is: why do these formulae work?

$\endgroup$
  • 1
    $\begingroup$ I didn't look at your specific polynomials, but you could look into "Padé approximants" to see if there is any relation. $\endgroup$ – Greg Martin Oct 25 '16 at 5:00
  • 1
    $\begingroup$ If $m^2=n$, then the result is $m$, which is exact! So, we have to find out, how $\frac{a}{b}$ depends on $\frac{m^2}{n}$, which will be always near $1$ if $n$ is large. $\endgroup$ – Peter Oct 25 '16 at 13:10
  • 1
    $\begingroup$ What might help : $m$ is just $\sqrt{n}$, correctly rounded to the next natural number. $\endgroup$ – Peter Oct 26 '16 at 9:41
  • 1
    $\begingroup$ @Peter Ah... I think I see what you're getting at. If you plug $m\approx\sqrt{n}$ into the formula then what comes out is $\frac{128 n^{4}}{128 n^{3.5}}$. That's awesome, if you could end up writing that up into an answer, and explain why my formula for $m$ is $\sqrt{n}$ rounded to the nearest integer, then I'll definitely accept your answer. If you might be able to give an intuitive explanation of just why the ratio of binomial terms that comes out of the near integer approximations gives a Pade approximant, then that would be even more awesome! $\endgroup$ – Anon Oct 26 '16 at 21:48
  • 1
    $\begingroup$ The perfect answer to this question would include a mention of what Barry has identified in his answer, as well as some explanation of the appearance of the Pade approximant. $\endgroup$ – Anon Oct 27 '16 at 2:50
9
$\begingroup$

Concerning the first question $$\sqrt{x}\approx\frac{x^4+112 x^3+1120 x^2+1792 x+256}{16 x^3+448 x^2+1792 x+1024}$$ is the $\text{Pade}_{(4,3)}$ expansion of $\sqrt x$ centered at $x=4$ (have a look here).

Around a given point, any function can be approximated using Padé approximants which are ratios of polynomial of selected degrees.

If you consider $\text{Pade}_{(4,4)}$, it would be $$\sqrt{x}\approx \frac{9 x^4+336 x^3+2016 x^2+2304 x+256}{x^4+144 x^3+2016 x^2+5376 x+2304}$$ which is much better.

For the same number of coefficients, Padé approximants are incredibly more powerful than Taylor expansions. For example, in the case you gave, over the range $3\leq x \leq 5$, the largest error is less than $2.5 \times 10^{-9}$ that is to say more than ten times smaller than the result of a Taylor expansion to $O\left((x-4)^8\right)$.

We could play a lot with this kind of work and be sure that it is used a lot for many problems.

$\endgroup$
  • $\begingroup$ That is very interesting. Now I wonder why taking binomial expansions of powers of small Pisot-Vijayaraghavan numbers gives a Pade approximant... Seems quite fascinating to me. $\endgroup$ – Anon Oct 25 '16 at 5:25
  • $\begingroup$ (any analytic function, otherwise the result can be weird) $\endgroup$ – reuns Oct 25 '16 at 5:26
  • $\begingroup$ Very good explanation. +1 for the same. $\endgroup$ – Paramanand Singh Oct 26 '16 at 7:28
8
$\begingroup$

It looks like the OP started with the observation that, when $(3+\sqrt8)^8$ is expanded into an expression of the form $a+b\sqrt8$, then $\sqrt8\approx a/b$, and similarly for other square roots. There is a fairly simple explanation for all this, based on examining the conjugate expression(s), $(3-\sqrt8)^8=(0.1715729\ldots)^8\approx0.00000075$.

If $(3+\sqrt8)^8=a+b\sqrt8$, then $(3-\sqrt8)^8=a-b\sqrt8$, hence $(3+\sqrt8)^8+(3-\sqrt8)^8=2a$. But since $3-\sqrt8=0.1715729\ldots$ is less than $1$, its eight power is much less than $1$, and so we have

$$2a=(3+\sqrt8)^8+(3-\sqrt8)^8\approx(3+\sqrt8)^8=a+b\sqrt8$$

from which $\sqrt8\approx a/b$ follows.

$\endgroup$
  • $\begingroup$ Thank you for that very simple and useful explanation. That explains perfectly why we can extract a good approximation for $\sqrt{n}$ from such powers, and also explains why the resulting formula is a ratio of binomial terms. Combined with Peter's insight about the role of the formula for $m$, I guess that pretty much explains everything I was wondering about. The only thing left to ask I guess is exactly why we get the Pade approximant. $\endgroup$ – Anon Oct 27 '16 at 2:48
  • $\begingroup$ This answer is much closer to the intent of the question, so I clearly prefer it to the answers above. It is an open question whether the resulting fraction actually is a Pade-approximant, I have doubts whether this is the case. $\endgroup$ – Peter Oct 27 '16 at 12:51
  • $\begingroup$ @Barry Cipra This answer of yours was the crucial step in helping me to understand why the formula was so accurate, even for noninteger $n$. I've written up my own answer just now putting everything together, but it's basically just extending the method of this answer of yours to all $m$ and $n$. This answer deserves another upvote! $\endgroup$ – Anon Nov 11 '16 at 3:21
1
$\begingroup$

This is related to Pell's equation $x^2-ny^2=1$, which is to be solved over the integers with $n$ as a parameter. For any non-square $n$ there is a infinite series of solutions. Given one or two solutions, another may be generated by the Brahmagupta-Fibonacci_identity. If you have two solutions $(a,b)$ and $(c,d)$, another solution will be $(ac+nbd, ad+bc)$, which you can verify by doing the algebra. For $n=2$ the base solution is $(3,2)$, which is followed by $(17,12), (577, 408)$ and so on. This given $\frac 32=1.5, \frac {17}{12}\approx 1.416666, \frac{577}{408} \approx 1.414216$ and so on as approximations to $\sqrt 2$

$\endgroup$
  • $\begingroup$ This is interesting, but some more explanation specifically relating to the formulae I mentioned would be useful. $\endgroup$ – Anon Oct 25 '16 at 5:16
1
$\begingroup$

From the many good answers and comments to this question, especially those of Peter and Barry Cipra, I think I’ve come to understand the answers to most of my questions. Since none of the answers by other users here has all of the information in one place, and someone else might want to see in one place what helped me at least, I thought I’d write it all up into one answer (I've accepted the answer to make it obvious, I hope that's not considered rude). The main thing I'm answering is my question about why powers of $(m+\sqrt{n})$ give good approximations of $\sqrt{n}$, and also finding the error of the approximation.

When $(m+\sqrt{n})^c$ is expanded binomially for $m,c\in\mathbb{N}$ and real $n>0$, we get:

$$(m+\sqrt{n})^c=\sum_{k=0}^{c}\binom{c}{k}m^k n^{\frac{c-k}{2}}$$

$$=\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}$$

Now if $c$ is even then a factor of $\sqrt{n}$ can be taken out of the second sum as follows:

$$\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}\\=\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}+\sqrt{n}\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k}{2}}$$

such that the powers of $n$ in each sum are all integers, and if $c$ is odd then the same factor can be taken out of the first sum so that all powers of $n$ in the sums are integers:

$$\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}\\=\sqrt{n}\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k-1}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}$$

This gives us the following:

$$(m+\sqrt{n})^c=a_{m,c}(n)+b_{m,c}(n)\sqrt{n}\tag{1}$$

Where $a_{m,c}$ and $b_{m,c}$ are polynomials in $n$ given by:

$$a_{m,c}(n)=\begin{cases}\sum_\limits{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}&c\text{ even}\\\sum_\limits{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}&c\text{ odd}\end{cases}$$

$$b_{m,c}(n)=\begin{cases}\sum_\limits{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k}{2}}&c\text{ even}\\\sum_\limits{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k-1}{2}}&c\text{ odd}\end{cases}$$

(Note that these polynomials are the polynomials found in the rational approximation in the question). Now an analogous argument will show that:

$$(m-\sqrt{n})^c=\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}(-1)^{\frac{c-2k}{2}}m^{2k}n^{\frac{c-2k}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}(-1)^{\frac{c-2k+1}{2}}m^{2k-1}n^{\frac{c-2k+1}{2}}$$

And if $c$ is even then we have:

$$(m-\sqrt{n})^c=\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}-\sqrt{n}\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k}{2}}$$

And if $c$ is odd then we have:

$$(m-\sqrt{n})^c=-\sqrt{n}\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k-1}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}$$

So that we must have:

$$(m-\sqrt{n})^c=a_{m,c}(n)-b_{m,c}(n)\sqrt{n}\tag{2}$$

Thus we can add $(1)$ and $(2)$ together to obtain: $$(m+\sqrt{n})^c+(m-\sqrt{n})^c=2 a_{m,c}(n)$$

$$\therefore 2 a_{m,c}(n)=a_{m,c}(n)+b_{m,c}(n)\sqrt{n}+(m-\sqrt{n})^c$$

$$\therefore b_{m,c}(n)\sqrt{n}=a_{m,c}(n)-(m-\sqrt{n})^c$$

$$\therefore \sqrt{n}=\frac{a_{m,c}(n)-(m-\sqrt{n})^c}{b_{m,c}(n)}$$

Thus we have proved that the following approximation:

$$\sqrt{n}\approx\frac{a_{m,c}(n)}{b_{m,c}(n)}$$

(which is exactly the form of the approximations in the question) will for any positive real number $n$ have an error $E$ of precisely:

$$E=\frac{|m-\sqrt{n}|^c}{b_{m,c}(n)}$$

since $b_{m,c}$ is positive. If $m$ is constrained to be an integer near $\sqrt{n}$ then it is easy to see that this will be small, especially for large $c$ (for which $b_{m,c}$ will also increase).

Now a quick check shows that the formula for $m$ in the question never differs from $\sqrt{n}$ by more than around $0.75$ for $n>1$ so the error for $c=8$ will be always less then around $\frac{1}{10 b_{m,c}(n)}$ which will grow as $b_{m,c}$ grows (indeed as $n$ increases the bound on the error appears to decrease towards $\frac{1}{256 b_{m,c}(n)}$ although I haven't proved this). This explains why the following formula for instance:

$$\sqrt{n}\approx\frac{m^{8}+28 m^{6}n+70 m^{4}n^{2}+28 m^{2}n^{3}+n^{4}}{8 m^{7}+56 m^{5}n+56m^{3}n^{2}+8m n^{3}}$$

$$m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$$

is such a good approximation.

Indeed if we constrain $m$ to be an integer then the closest to $\sqrt{n}$ we could choose is $\left\lfloor\frac{1}{2}+\sqrt{n}\right\rfloor$ in which case the error of the approximation would be always less than $\frac{1}{2^{c}b_{m,c}(n)}$ which will be very small. This appears to explain the accuracy of the formulae shown.

$\endgroup$

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.