11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 3 + sqrt(1/50) isn't too shabby. Gerhard "That's Without Pencil And Paper" Paseman, 2020.01.28. $\endgroup$ – Gerhard Paseman Jan 29 at 6:20
  • 1
    $\begingroup$ 4-sqrt(14/19) is more than an order of magnitude better (but not without pencil and paper!) $\endgroup$ – Bruce Blackadar Jan 29 at 15:53
  • $\begingroup$ Such numbers have eventually periodic continued fractions. Maybe something can be done comparing periodic continued fractions to the continued fraction of $\pi$? $\endgroup$ – Will Sawin Jan 29 at 16:48
  • $\begingroup$ 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. $\endgroup$ – Will Sawin Jan 29 at 18:03
  • 1
    $\begingroup$ Below $100$, only one stands out: $71/28+\sqrt{29/79}$. Next best is $-47/46+\sqrt{52/3}$, far behind. $\endgroup$ – Yaakov Baruch Jan 29 at 18:13
6
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ An approximation using $22$ digits, and good to $10^{-22}$. About what one might expect, no? $\endgroup$ – Gerry Myerson Jan 31 at 5:02
  • 2
    $\begingroup$ 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. $\endgroup$ – Jeremy Rouse Jan 31 at 12:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Yaakov Baruch Feb 1 at 22:12
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Yaakov Baruch Feb 1 at 22:49

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.