# Approximations to $\pi$

Is there a way to efficiently solve the following problem besides brute-force calculation?

Fix $$n\in\mathbb{N}$$ (say $$n=100$$). Find the integers $$p,q,r,s$$ with $$0\leq p,q,r,s\leq n$$ such that $$\pm\frac{p}{q}\pm\sqrt{\frac{r}{s}}$$ most closely approximates $$\pi$$.

Some cases can be handled by finding the continued fraction expansion of $$(\pi-\frac{p}{q})^2$$ for various $$p,q$$. Playing with this method I found the approximation $$4-\sqrt{\frac{14}{19}}$$, which is really quite good, but may not be best for $$n=20$$. Note that the solution will be unique (for a given $$n$$).

• 3 + sqrt(1/50) isn't too shabby. Gerhard "That's Without Pencil And Paper" Paseman, 2020.01.28. Jan 29 '20 at 6:20
• 4-sqrt(14/19) is more than an order of magnitude better (but not without pencil and paper!) Jan 29 '20 at 15:53
• Such numbers have eventually periodic continued fractions. Maybe something can be done comparing periodic continued fractions to the continued fraction of $\pi$? Jan 29 '20 at 16:48
• I guess the key to that approach would be to give an upper bound for $\max(p,q,r,s)$ in terms of the continued fraction, enabling a (hopefully) efficient search over periodic continued fraction approximations. Jan 29 '20 at 18:03
• Below $100$, only one stands out: $71/28+\sqrt{29/79}$. Next best is $-47/46+\sqrt{52/3}$, far behind. Jan 29 '20 at 18:13

This is not exactly an answer to the stated question, but it's too long for a comment. Rather than the form given in the question, one could represent a number in the form $$\frac{a + b \sqrt{d}}{c}$$, where $$d$$ is a squarefree positive integer, and this form lends itself to finding good approximations to $$\pi$$ using lattice reduction.

Fix a bound $$n$$. For each squarefree $$d$$ with $$1 \leq d \leq n$$, choose a constant $$X \approx n^{2} \sqrt{d}$$ and create the lattice in $$\mathbb{R}^{4}$$ spanned by $$v_{1} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ X \pi \end{bmatrix}, v_{2} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ -X \end{bmatrix}, v_{3} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ -X \sqrt{d} \end{bmatrix}.$$

A short vector in this lattice with respect to the $$\ell_{2}$$ norm is a linear combination $$a v_{1} + bv_{2} + cv_{3}$$ and because the fourth coordinate of these vectors are so large, this forces $$\frac{a+b \sqrt{d}}{c}$$ to be a close approximation to $$\pi$$.

Finding the shortest vector in a lattice is a hard problem, even in small dimensional lattices. However, one can get within a constant multiple of the true minimum using the LLL-algorithm. With this, the above algorithm would run in time $$O(n \log^{3} n)$$ and find "some good solutions", but isn't guaranteed to find the optimal representation (even in this modified form).

I ran this with $$n = 10^{6}$$ and $$X = n^{2} \sqrt{d} \log(n)$$ and obtained (after about a minute and a half) $$\pi \approx \frac{-327031 + 7075 \sqrt{224270}}{962406}.$$ The approximation differs from the truth by about $$8 \cdot 10^{-22}$$.

• An approximation using $22$ digits, and good to $10^{-22}$. About what one might expect, no? Jan 31 '20 at 5:02
• To answer Gerry Myerson's question - yes, this is about as good (or even a little worse) an approximation as one would expect. Perhaps I wasn't clear above - for a fixed $d$ the lattice reduction is polynomial time and takes about $O(\log^{3} n)$, and so looping over all $d$, the runtime is something like $O(n \log^{A} n)$ for some $A$ depending on how quick the arithmetic is. Jan 31 '20 at 12:21
• A brute force search to find $\pi \approx (a+\sqrt{b})/c$ can be done with a loop of the form for(a=-n; a<=n; a++) for(c=max(1,int((a-sqrt(n))/pi)); c<=min(n,(a+sqrt(n))/pi); c++) {b=...} and therefore $O(n^{3/2}\log^A)$ operations for some small $A$ that I'm not sure about. Not too much worse than the clever but non-optimal scheme suggested here. However notice that I have $\sqrt{b}$ here rather, than the $b\sqrt{d}$ of this answer. Feb 1 '20 at 22:12
• In under 3 minutes, for $n=10^6$, the best, unexciting approximation $\pi\approx (108062-\sqrt{99097})/34297$ is found, good to about $4 \cdot 10^{-16}$. Feb 1 '20 at 22:49