Suppose we have a (real) number x and we want to approximate it by a fraction. For example, π ≈ 3.14159265… could be approximated as 22/7, or as 314159/100000. In fact, for each denominator q = 1, 2, 3, …, we could approximate x by a fraction p/q, where the best choice for p is the integer closest to xq. Roughly speaking, we can get closer approximations by using larger denominators.

If we fix a certain “budget” of how large the denominator is allowed to be, then what is the closest approximation we can achieve? Usually, the answer is not simply to use the largest denominator: for example, rather than choosing the denominator 100 to approximate π as 314/100=3.14, it is better to choose the smaller denominator 99 and approximate π as 311/99≈3.14141414…. Such fractions that give the best result for a given “budget” are called best rational approximations. We can state this more precisely:

Definition: Given a number x, its best rational approximations of the first kind are those fractions p/q such that x is closer to p/q than to any fraction with a smaller denominator. In other words, for any fraction p′/q′ with q′ < q, we have |x-p′/q′| > |x-p/q|.

For π, the fraction 311/99 is a best rational approximation (of the first kind), while 314/100 is not. Apart from asking for the best fraction under budget, we can also ask for the best “bang for the buck”. Is it worth doubling our denominator budget, say, if the error doesn't even get halved? For example when we move from 22/7 to 311/99, the denominator increased by over 14 times, while the error only decreased by about 7 times. So relative to the denominator, the error in 311/99 is still somewhat large. On the other hand, 333/106 really is (slightly) better than 22/7 even relative to the denominator, because the denominator increased by a factor of less than 15.15, while the error decreased by a factor of more than 15.19. Here what we care about is not the absolute error itself, but the product of the error and the denominator used. To state this more precisely:

Definition: Given a number x, its best rational approximations of the second kind are those fractions p/q such that for any fraction p′/q′ with q′ < p, we have |q′x - p′| > |qx - p|.

These are a subset of the former: the rational approximations that are especially good even among the best rational approximations of the first kind. Another way of looking at them is that as we pick for each successive denominator q the closest integer p to xq (as mentioned in the first paragraph above), these are the cases for which the closest integer (p) is closer than ever before to the desired value (xq).

It turns out that there is a simple and fast algorithm to enumerate all such best rational approximations of any given number. (It also turns out that 355/113 is an amazingly good approximation of π, as it requires much larger denominators to beat it.) Here's a demonstration below (requires your browser to support BigInt).

Enter your own desired fraction (e.g. 0.25 or 1/3): 

The fraction is .

Its best bestest rational approximations with denominator at most , and for each its decimal value and error (to digits):

(Caveat: These are approximations for the fraction you entered (e.g. 3.14159265), and possibly not for the actual number (e.g π) you approximated by the fraction you entered. See source repo for details on this “bug”.)

How does this work? I hope to write this up in more detail later, but in short: (1) every real number can be represented as a continued fraction, (2) the best rational approximations of the second kind are all convergents of the continued fraction, and (3) the best rational approximations of the first kind are, additionally, about half of the semi-convergents / intermediate fractions. See for example pages 22 to 28 of Khinchin's classic book on continued fractions. Or puzzle your way through the source code. A related blog post from a few years ago.