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

Question

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.

Answer 1

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.

Answer 2

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.