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 .
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.