Optimal Fixed-Digit Rational Approximations of $\pi$

Question

Is there a systematic way of finding optimal rational approximations to $\pi$ whose numerator and denominator have at most $n$ digits?

More precisely:

Let $D_n$ be the set of all positive integers with at most $n$ digits and define the equivalence relation $\sim$ on $D_n\times D_n$ by $(x,y) \sim (x',y')$ iff $\frac{x}{y} = \frac{x'}{y'}$. For each fixed $n$, is there a systematic way to decide which equivalence class $[x,y]$ in $D_n\times D_n/\sim$ minimizes the residual $R(x,y) = \left|\frac{x}{y} - \pi\right|$?

For example, the optimal $D_1$ approximation is $[3,1] = \{(3,1),(9,3)\}$.

Note: it has been pointed out that you can always do this with a brute-force algorithm. That's obvious and not interesting. What is interesting is an efficient algorithm for doing this.

A philosophical point: clearly we have really, really, really good decimal approximations of $\pi$ and so rational approximations are of limited practical interest. This is therefore a question that arises from the enjoyment of mathematics for its own sake and not for its practical application.

Answer 1

There is. Just use any approximation method you want for $\pi$, and then calculate the differences between these approximations and the fractions you have, and take the fraction with the smallest difference.

But what I suspect is that you wanted a fast algorithm to do this. If anybody knew a method that was faster than our fastest known algorithm for computing digits of pi, well, that's a bit of a contradiction.

Otherwise, you can again use the fastest approximation for pi we have. Once you have sufficiently many digits, use the method of computing continued fractions and thus convergents to find the best approximations for pi.

Hope that helped.

Answer 2

The best approximations of any irrational number are given by the finite convergents of its continued fraction. For $\pi$, its continued fraction begins $$[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]\;\;\;\;. $$ It is not known to have any pattern, but it has been extensively tabulated. The numerators of these fractions have also been tabulated, and the first few are $$3, 22, 333, 355, 103993, 104348, 208341, 312689, 833719, 1146408, ...$$ To find the optimal $D_n$ approximation of $\pi$, simply choose the largest number on this list with $n$ or fewer digits and that will be the numerator of the fraction. Note that this means the optimal $D_3$, $D_4$, and $D_5$ approximations of $\pi$ are all $355/113$.