0

Just something I thought of and I'm curious about.

Say I tell you

I want to approximate $\pi$ using a rational number. However, I am going to tell you that the numerator is to be at most $m$ digits and the denominator is to be at most $n$ digits

Given a pair $(m,n)$, we can of course find some approximation to $\pi$. For example, if you give me $(2,1)$, then the answer is $\frac{22}{7}$.

My question is, given any pair $(m,n)$, is there such a thing as a 'best' rational approximation?

If there is such a thing, is it possible to acquire tight bounds for the degree of error in terms of $m$ and $n$?

Trogdor
  • 10,331
  • Since any such pair has finitely many rational numbers satisfying it we can always find a best one by simply enumerating and checking distances. I've no idea about error bounds, or what to do if you want to find the best one without precomputed knowledge of $\pi$. – zibadawa timmy Nov 09 '14 at 12:49
  • I do wonder if there is a way to find a best one, perhaps algorithmically, without actually enumerating the fraction and checking its value with respect to $\pi$. – Trogdor Nov 09 '14 at 12:51
  • I think that you should only constrain the number of digits in the denominator. The number of digits in the numerator will be determined by the denominator and the actual number. So for $\pi$ it is impossible to find a $(3,1)$ fraction unless you're going to permit "bad" approximations like $\frac{100}{9}$. Having said that, given values for $m$ and $n$ it is possible to determine approximate bounds for your error. – tomi Oct 20 '16 at 21:21
  • Wikipedia has a section on how to find best rational approximations defined as better approximations than any with smaller denominators based on the continued fraction. This would be taking the denominator to be like $999$ – Ross Millikan Oct 20 '16 at 22:55

1 Answers1

0

I think there are three parts to your question.

Q1) Is there such a thing as a "best rational approximation" to a number given certain constraints to the fraction?

Q2) Is there a way to determine the possible error in such an approximation?

Q3) Can the above be done for $\pi$?

I will attempt to answer the first two of those questions:

A1) Yes. If you know the true value $x$, then you want to minimise the difference between the true value and the estimate $X=\frac pq$.

$$\min_{1 \le q < 10^n , 1\le p<q}\left(|X-x|\right)$$

This looks like a lot of work, searching through all possible fractions, but we can cut down some of the effort by noting that if $\frac pq \approx x$, then $p \approx qx$. We can therefore try to find:

$$\min_{1 \le q < 10^n} \left(\left|\frac {\lfloor qx \rfloor}q -x \right|,\left |\frac {\lceil qx \rceil}q -x \right |\right)$$

This still involves searching through all the possible values of $q$.

A2) For a given value of $n$, the largest possible error is $\frac 1{2(10^n-1)}$, but this only occurs if $x$ is very close to 0 or 1.

A3) The above depends on knowing the true value $x$. If you don't have an approximation for $\pi$ then you can't really answer the question.

tomi
  • 9,594