1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It is worthwhile remarking that the topic of rational approximation of real numbers has a very beautiful theoretical development based not on decimal approximations but instead on continued fraction approximations. For example, using the continued fraction $$\pi = [3;7,15,1,292,...] = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{292 + ...}}}$$ one obtains the first approximation $\pi \approx 3 + \frac{1}{7} = \frac{22}{7}$, the second approximation $\pi \approx 3 + \frac{1}{7 + \frac{1}{15}} = \frac{333}{106}$, and so on. $\endgroup$ – Lee Mosher Jun 1 at 19:24
  • $\begingroup$ To address your final "philosophical" point, the mathematical theory of continued fraction approximations is much richer and more beautiful than the theory of decimal approximations, which is exactly why mathematics are attracted to it for its own sake. $\endgroup$ – Lee Mosher Jun 1 at 19:28
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 1) Yes, of course you can do this (and many other things) using brute-force. That's no so interesting. 2) I am not asking about fast approximation of $\pi$ itself. I am asking about (efficient) methods of finding optimal rational approximations of $\pi$ with a fixed number of digits in numerator and denominator. For example, I can know that $\pi \approx 3.1415926$ but not know what fraction with at most three digits in the numerator and denominator is the best approximation of $\pi$. $\endgroup$ – Mortified Through Math Jun 1 at 19:07

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.