# How do you find "good" rational approximations to a decimal number?

When presented with real number as a decimal, are there any methods to finding "good" rational approximations $$a/b$$ to that number? By "good" I mean that $$a$$ and $$b$$ are reasonably small integers. For example suppose you're handed the number $$1.7320508075688772935274463415058723 \dots$$ An obvious way to rationally approximate this numbers is to truncate it after the $$-n$$th decimal place and place it over $$10^n$$. So $$\frac{173}{100} \quad\text{or}\quad \frac{1732050807}{1000000000} \quad\text{or}\quad \frac{1732050807568877}{1000000000000000}$$ are increasingly good rational approximations. A way I can see to improve this is if you chose to truncate at a multiple of $$2$$ or $$5$$, your rational approximation will reduce to one that is more "good". For example $$\frac{1732}{1000} = \frac{433}{250} \qquad\text{and}\qquad \frac{173205}{100000} = \frac{34641}{20000}$$ Is there a clever way to see which multiples of $$2$$ of $$5$$ to truncate after to get a rational approximation that reduces a lot? This works because we express the decimal in base $$10$$, so are there any tricks considering the number in a different base? Is there an idea that's not even on my radar?

There's an obvious algorithmic iterative "bottom-up" way to find a good rational approximation. It's not terribly clever though. I can type it up as an answer in a second if no one else wants to.

• Try the continued fraction Nov 10, 2021 at 16:25
• Yes. Here is a link. This is exactly what continued fractions are good at. Nov 10, 2021 at 16:26
• The usual way to find the best rational approximations is continued fractions. But are you looking to have the best approximation overall or specifically one with a "nice" denominator? Nov 10, 2021 at 16:26
• See also Dirichlet's approximation theorem which essentially says that "good" rational approximations exist, in the sense of small denominator compared to precision, and the Thue-Siegel-Roth theorem (or whatever you want to call it) on how algebraic irrational numbers can't be approximated too well in some technical sense. Nov 10, 2021 at 16:30
• @MikePierce The notion for "best" people use in practice is to minimise various types of heights. The measure you suggest is essentially the naive height, where $H(p/q) = \max\{|p|,|q|\}$ for a rational number $p/q$ written in reduced form. Nov 10, 2021 at 16:33

This is exactly what continued fractions are for.

The continued fraction of $$\sqrt 3=1.7320508075688772935274463415058723\ldots$$ is periodic: $$[1; 1, 2, 1, 2, 1, 2, 1, 2, \ldots]$$. The sequence of approximants is $$2,\frac53,\frac74,\frac{19}{11},\frac{26}{15},\frac{71}{41},\ldots$$ ; each of these is the best possible approximant for its denominator. For instance, $$\frac{19}{11}$$ is the best approximant with a denominator $$\le 11$$.

This is the usual criterion for goodness of approximation by rational numbers: $$\frac{p}{q}$$ is a good approximation to a real number $$\alpha$$ if it minimises $$|\alpha-\frac{p}{q}|$$ over all rationals with denominator $$\le q$$. Powers of ten shouldn't come into it at all.

I looked into this topic too, since i wanted a way to list all fractions in a small sub-interval of $$[0,1]$$. If you just want to look at an implementation that does this I attached some typescript code. My approach came from looking into the Farey sequence $$\cal F_n$$. One can show that if $$a/b$$ and $$c/d$$ are fractions such that no other fraction $$e/f$$ with $$a/b < e/f < c/d$$ and $$f \leq \max(b,d)$$ exists, then $$\frac{a+c}{b+d}$$ is the fration with the smallest denominator between $$a/b$$ and $$c/d$$.

For our case we choose a number $$v \in (0,1)$$ that we want to approximate. Formulating this as an algorithm we can start with the lower bound $$a / b = 0/1$$ and upper bound $$c/d = 1/1$$. Next we define $$\frac{e}{f} = \frac{a+c}{b+d}.$$ Now 3 possible cases can happen. If $$f$$ is too large, the best approximation for $$v$$ is either $$a/b$$ or $$c/d$$. Otherwise we have have $$e/f < v$$ or $$e/f \geq v$$. If $$e/f < v$$ replace $$a/b$$ by $$e/f$$ and repeat the steps. In the other case replace $$c/d$$ by $$e/f$$. More formally:

Choose: A value $$v$$ to approximate and the maximum denominator $$Q$$.

Initialize: $$a/b := 0/1$$ and $$c/d := 1/1$$.

Iterate: for $$a/b < v \leq c/d$$:

• Evaluate: $$e/f := (a+c)/(b+d)$$.
• If $$f \geq Q$$: Return $$a/b$$ or $$c/d$$.
• If $$e/f < v$$: Replace $$a/b := e/f$$ and begin next iteration.
• If $$v \leq e/f$$: Replace \$c/d := e/f and begin next iteration.

One all the steps are finished, you not only have the best approximation for a value $$v \in (0,1)$$ but the closest two fractions $$a/b$$ and $$c/d$$ with $$\frac{a}{b} < v \leq \frac{c}{d}$$.

This algorithm is what I started out with. It has worst case complexity $$O(Q)$$ time and $$O(1)$$ space. One can improve the algorithm by batching up multiple steps. I did not prove the complexity, but I think the improved version has complexity $$O(\log Q)$$ time and $$O(1)$$ memory. I will attach some Typescript code for this improved algorithm.

/**
* Returns the two fractions closest to $$v$$ with $$a/b <= v <= c/d$$. One always has $$a/b \neq c/d$$.
*
* # The Algorithm:
*
* Chooses $$\frac{a^+}{b^+} = \frac{a + e_1 c}{b + e_1 d} <= v$$ with $$b + e_1 d <= Q$$ in the first,
* and $$\frac{c^+}{d^+} = \frac{e_2 a^+ + c}{ e_2 b^+ + d} >= v$$ with $$e_2 b + d <= Q$$ in the second step.
* Iterate until nothing happens anymore.
*
* If $$0 < v < 1$$, the final fractions will be consecutive elements in the Farey sequence $$F_Q$$.
*/
function findLowerAndUpperApproximation(v: number, Q: number) {
// Ensure v in [0,1)
let v_int = Math.floor(v);
v = v - v_int; // only use fractional part of $$v$$ for iteration
let a = 0,
b = 1,
c = 1,
d = 1;

while (true) {
let _tmp = c - v * d; // Temporary denominator for 0 check

// Batch e1 steps in direction c/d
let e1: number | undefined;
if (_tmp != 0) e1 = Math.floor((v * b - a) / _tmp);
if (e1 === undefined || b + e1 * d > Q) e1 = Math.floor((Q - b) / d);

a = a + e1 * c;
b = b + e1 * d;

_tmp = b * v - a; // Temporary denominator for 0 check

// Batch e2 steps in direction a/b
let e2: number | undefined;
if (_tmp != 0) e2 = Math.floor((c - v * d) / _tmp);
if (e2 === undefined || b * e2 + d > Q) e2 = Math.floor((Q - d) / b);

c = a * e2 + c;
d = b * e2 + d;

// If both steps do nothing we are done
if (e1 == 0 && e2 == 0) break;
}

return [v_int*b + a, b, v_int*d + c, d];
}


In each step the denominator of $$c/d$$ should at least double. This would result in complexity $$O(\log Q)$$. However, i haven't worked out the details here. For me the algorithm is good enough to find the best fractions for $$Q = 10^9$$. Going past that my code seems to hit machine precision problems, which most likely affect the divisions in the algorithm. When you use a language with higher precision integer division you should be fine to go almost as far as you want.