Approximation game - lcamtuf’s thing

lcamtuf’s thing

SubscribeSign in

Approximation game<br>The number 22/7 and the pigeon flocks of Peter Gustav Lejeune Dirichlet<br>Feb 28, 2026

12

Share

In some of the earlier articles on this blog, we talked about the nature of real numbers and the meanings of infinity. The theory outlined in these posts is interesting but also hopelessly abstract. It’s as if we’re inventing make-believe worlds that have no discernible connection to reality.<br>In today’s post, we’ll examine a cool counterexample: an outcome of an numerical experiment that can be backed up with fairly simple proofs, but that makes sense only if you take a step back to consider the construction of real numbers and rationals.<br>We start by picking a real number r. Your job is to approximate it as closely as possible using a rational fraction a / b with a reasonably small denominator. The approximation can’t be the same as r. Is this task easier if r itself is rational or irrational?<br>Make a guess and let’s dive in. For simplicity, we’ll stick to a positive r and positive fraction denominators throughout the article.<br>Defining “good”

For a chosen denominator b, it’s pretty easy to find the value of a that gets us the closest to the target r. We must consider two cases: the largest “low-side” fraction that’s still less than r; and the smallest “high-side” fraction greater than r. If there’s a rational fraction that matches r exactly, that solution is prohibited by the rules of the game; we need to pick one of the nearby values instead.<br>If you wanted to find an exact match, you could try aideal = r · b; this makes the a / b fraction equal to r · b / b = r. That said, r · b might not be an integer (or even a rational number), so even without the added “no exact matches” rule, the approach is usually a bust.<br>If we round the value up (⌈r · b⌉), we get a number that is equal or greater than aideal; if it’s greater, the difference between the two values will be less than 1. In other words, we can write the following inequality:<br>\(a_{ideal} \leq\lceil r · b\rceil

This is saying that the rounded-up number may be equal to the ideal solution needed to match r exactly, or it might overshoot the target, but always by less than the minimum possible increment of the numerator in the a / b fraction.<br>The result is almost what we need, but once more, the rules prohibit approximations that are exactly equal to r. The workaround is to subtract 1 from all sides of the inequality:<br>\(a_{ideal} - 1 \leq \lceil r · b \rceil -1

The effectively tells us that the middle term — ⌈r · b⌉ - 1 — is always less than the value needed to match r, but the difference is never greater than a single tick of the numerator. We’re as close as we can be; the value of a for the optimal low-side approximation (a / b r) is:<br>\(a_{low} = \lceil r \cdot b \rceil - 1 \)

We can follow the same thought process to find the high-side estimate (a / b > r); this time, we round the product down and then add 1:<br>\(a_{high} = \lfloor r \cdot b \rfloor + 1<br>\)

Finally, the error (ε) associated with any a / b can be easily calculated as:<br>\(\varepsilon = \biggl|r - \frac{a}{b}\biggr|\)

Earlier in the process, we have established that if we pick alow or ahigh, the error can’t exceed one tick of the numerator, which works out to a difference of ± 1/b. As a practical example, if we’re trying to approximate r = 2 using b = 5, the best inexact solutions are 9/5 = 1.8 on the low side and 11/5 = 2.2 on the high side; they both have an error of 1/b = 0.2.<br>Next, we’ll try to examine if the error can be less. If we find any approximations that are better than the worst-case scenario — i.e., that satisfy ε b — we’re gonna call them 1-good.<br>As an inspection aid, we can also define a denominator-normalized approximation score s, calculated by multiplying ε by b:<br>\(s = \varepsilon \cdot b\)

This keeps the maximum error at 1 regardless of the denominator we’ve chosen. By that metric, a 1-good approximation is associated with s<br>The rational test case

Now that we have the mechanics spelled out, let’s take r = 1/4 and analyze the optimal solutions for some initial values of b:<br>\(\begin{array}{|r|c|c|c|l|}<br>\hline<br>\mathbf{b} & \textbf{Best a/b} & \textbf{Error (ε)} & \textbf{Score }\mathbf{(s)} & \textbf{1-good?} \\<br>\hline<br>1 & 0/1 & 1/4 & 1/4 & yes\\<br>\hline<br>2 & 0/2 & 1/4 & 1/2 & yes\\<br>\hline<br>3 & 1/3 & 1/12 & 1/4 & yes \\<br>\hline<br>4 & 0/4 & 1/4 & 1 & no \\<br>\hline<br>5 & 1/5 & 1/20 & 1/4 & yes \\<br>\hline<br>6 & 2/6 & 1/12 & 1/2 & yes\\<br>\hline<br>7 & 2/7 & 1/28 & 1/4 & yes\\<br>\hline<br>8 & 1/8 & 1/8 & 1 & no\\<br>\hline<br>9 & 2/9 & 1/36 & 1/4 & yes\\<br>\hline<br>10 & 2/10 & 1/20 & 1/2 & yes\\<br>\hline<br>\end{array}\)

We find that many approximations are 1-good (ε b, s b baseline by small factors that are stuck on repeat. If we plot a larger sample, we get:

Approximation scores for r = 1/4.<br>In this log-scale plot, I also included a diagonal line that represents error values decreasing with the square of the denominator...