Approximation of rational numbers

Question

The question is stated thus:

Find fractions of the form $\frac{a}{b}$ where $|b| \leq 10$ which are as close as possible to the following fractions:

(a) $\frac{660}{563}$

(b) $\frac{2344}{733}$

(c) $0.150493827$

No other information was provided with the question besides the fact that from context it may be inferred that $\frac{a}{b}$ must be a rational number.

My first impulse is to grab a calculator and find the $a,b \in \mathbb{N}\ , \ 0 < b \leq 10\ $ whose quotient $\frac{a}{b}$ has the closest decimal value to that of the fraction in the question by guessing and checking. That method might provide a solution which is technically correct but there isn't really any mathematical thought behind it and "I tried like twenty different combinations and I promise this is the best one" is obviously not a valid explanation for said answer.

My next thought was to divide the numbers in the numerator and denominator by the appropriate power of $10$ , round the resulting real numbers up or down to integers and hoping for the best. While slightly more theoretically methodical than checking at random, it still involves a degree of guesswork which I don't believe this problem necessitates. Moreover, this method worked for the fraction (a) but not for (b), so it can't be applicable for any fraction.

I've also tried solving inequalities of the form $\frac{a-1}{b-1} < \frac{660}{563} < \frac{a+1}{b+1}$ and several variations thereof and they all seem to reach a methodical conclusion similar to the second approach outlined above.

Basically, how can I solve this problem with 100% fidelity for any given fraction using a method that isn't based on intuitive guesswork?

Answer 1

Every best rational approximation $r$ of a real number $x$ (in the sense that $|r - x| < |s-x|$ for every other rational number $s$ with the same or smaller denominator) is either a convergent or an intermediate fraction of the continued fraction representation of $x$.

Answer 2

I'm not sure this is guaranteed to give the best estimate for any given bound on the numerator and denominator, but generally you get very good estimates relative to the size of the denominator by taking continued fraction convergents. For rational numbers it goes like this. Split a number into integer and fractional part:

$$660/563 = 1+97/563.$$

Next you write the fractional part $f=(f^{-1})^{-1}$ and repeat the procedure on $f^{-1}$. So the second stage is

$$660/563=1+(5+78/97)^{-1}.$$

At any point you can terminate and obtain an upper and lower bound by replacing the trailing fraction by $0$ and $1$. Thus for instance at the start you obtain the rather boring bound

$$1 \leq \frac{660}{563} \leq 2$$

and at the second stage you obtain the more interesting bound

$$\frac{7}{6} \leq \frac{660}{563} \leq \frac{6}{5}.$$

There is a way to use a slight variant of the Euclidean algorithm to do this efficiently without having to write down all these equations along the way. In the first step you take the quotient and remainder $(q,r)$ when dividing $a/b$; you record $q$ for the final answer and then compute the quotient and remainder $(q',r')$ when dividing $b/r$; you record $q'$ for the final answer and then compute the quotient and remainder $(q'',r'')$ when dividing $r/r'$; etc. Eventually for a rational number this will terminate; the last nonzero remainder will be the greatest common factor of $a$ and $b$. (The only difference between this and the Euclidean algorithm for finding the greatest common factor is that you record the intermediate quotients.)

Note that a decimal number is a special case of the same thing, where the denominator is just $10^n$ for some $n$.

Answer 3

For each real number $x$, you can go down the Stern–Brocot tree locating $x$, recording the best rational approximations that have denominator in the given range, taking the best approximations found at each step.