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

Improve this question
$\endgroup$
13
  • $\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, 2020 at 6:20
  • 2
    $\begingroup$ 4-sqrt(14/19) is more than an order of magnitude better (but not without pencil and paper!) $\endgroup$
    – Bruce Blackadar
    Jan 29, 2020 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, 2020 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, 2020 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, 2020 at 18:13

1 Answer 1

Reset to default
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}$.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ An approximation using $22$ digits, and good to $10^{-22}$. About what one might expect, no? $\endgroup$
    – Gerry Myerson
    Jan 31, 2020 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, 2020 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, 2020 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, 2020 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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