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.

  • 7
    $\begingroup$ Try the continued fraction $\endgroup$
    – Henry
    Nov 10, 2021 at 16:25
  • 1
    $\begingroup$ Yes. Here is a link. This is exactly what continued fractions are good at. $\endgroup$
    – TonyK
    Nov 10, 2021 at 16:26
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 10, 2021 at 16:26
  • 2
    $\begingroup$ 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. $\endgroup$
    – prets
    Nov 10, 2021 at 16:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – prets
    Nov 10, 2021 at 16:33

2 Answers 2


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .