# How can I efficiently find the "simplest" rational in an interval?

For a hobby software project I am working with exact rational arithmetic, as it happens this produces numbers $$\frac{n}{k}$$ of huge size even after reducing them, I am searching for an efficient algorithm to "simplify" these rational with a specified error tolerance.

In my own working out the "simplicity function" I was trying to maximize was $$S(\frac{n}{k}) = |\frac{1}{k}|$$ because it seemed the simplest.

In the following I will focus on finding a rational with minimal denominator, but if you have a solution with a different definition of "simple rational" that still decreases $$\log(n) + \log(k)$$ it would still solve my problem.

So given 2 rational numbers $$p,q \in \mathbb{Q}$$ with $$p\lt q$$, and a $$k \in \mathbb{N}^+$$ we can find a rational $$\frac{n}{k}$$ s.t. $$p \le \frac{n}{k} \le q$$ iff $$\lceil kp\rceil \le\lfloor kq\rfloor$$ by choosing $$n \in \left[\lceil kp\rceil,\lfloor kq\rfloor\right]\cap\mathbb{Z}$$.

Also if $$k \ge \frac{1}{q-p}$$ then the set $$\left[\lceil kp\rceil,\lfloor kq\rfloor\right]\cap\mathbb{Z}$$ is never empty.

Is there a simply way to find the minimal $$k$$ such that $$\lceil kp\rceil \le\lfloor kq\rfloor$$?

In a sense this could be more mathematically formulated as finding a global maximum of a function like $$$$f(n,k) = \left\{ \begin{array}{lll} \frac{1}{k} & \text{if} & p \le \frac{n}{k} \le q \\ 0 & \text{if} & \text{otherwise} \end{array} \right.$$$$ Or

$$$$f(n,k) = \left\{ \begin{array}{lll} \frac{1}{\log(|n|)+\log(|k|)} & \text{if} & p \le \frac{n}{k} \le q \\ 0 & \text{if} & \text{otherwise} \end{array} \right.$$$$

But since it came from an algorithmic context I preferred to keep it in a semi-algorithmic formulation.

• I'd look at continued fraction algorithms Jun 11 at 15:41
• Yeah, something like “consider an unspecified $x$ such that $p≤x≤q$, start computing the continued fraction of $x$ based on interval calculations, and stop when the floor can no longer be computed”. Jun 11 at 18:09
• This is probably abstractly equivalent to pruning the Stern-Brocot tree to keep only the branches lying in the specified interval, and stop as soon as a node lies in it. But I realize there's some work to be done to formulate this as an actual usable algorithm. Jun 11 at 18:11
• See also Exercises 4.5.3.39 and 4.5.3.40 in Knuth's Seminumerical Algorithms. Jun 30 at 17:16

Here's a version of what has been said in the comments that's reformulated into an explicit algorithm, first assuming that $$p$$ and $$q$$ are irrational to avoid the edge case:

• Lazily compute the continued fraction expansions of $$p = [a_0; a_1, a_2, a_3,\ldots]$$ and $$q = [b_0; b_1, b_2, b_3,\ldots]$$: stop at the first $$i$$ such that $$a_i \neq b_i$$ (namely $$a_i < b_i$$ if $$i$$ is even, and $$a_i > b_i$$ if $$i$$ is odd, all this is for $$p).

• The sought-after rational is then $$[a_0; a_1, a_2, a_3,\ldots, a_{i-1},\min(a_i,b_i)+1]$$.

Indeed, this is clear from the paths taken in the Stern-Brocot tree: the branch toward $$p$$ from the root proceeds by going $$a_0$$ steps to the right, then $$a_1$$ to the right, then $$a_2$$ to the left, and so on; and similarly for $$q$$ with $$b_j$$ instead of $$a_j$$. The properties of the Stern-Brocot tree make it clear that the sought-after rational is the node of first divergence between these two branches; now the continued fraction expansion of the rational node in question is obtained by tacking a final $$1$$ to the common sequence, so it's $$[a_0; a_1, a_2, a_3,\ldots, a_{i-1},\min(a_i,b_i), 1]$$ which is more standardly written as $$[a_0; a_1, a_2, a_3,\ldots, a_{i-1},\min(a_i,b_i) + 1]$$.

If $$p$$ and/or $$q$$ are rational the same procedure applies provided we take the continued fraction expansion of the form $$[a_0;a_1,\ldots,a_r,1]$$ and/or $$[b_0;b_1,\ldots,b_s,1]$$, because again this tells us that $$p$$ is reached in the Stern-Brocot tree by going first $$a_0$$ steps to the left, then $$a_1$$ to the right, and ending in $$a_r$$ steps in the final direction (and stop there):

• If there is $$i\leq\min(r,s)$$ such that $$a_i\neq b_i$$, this is exactly as above.

• If $$s\geq r$$ and $$b_i = a_i$$ for all $$0\leq i\leq r$$, then the sought-after rational is $$p = [a_0;a_1,\ldots,a_r,1]$$ itself (it is an ancestor of $$q$$ in the Stern-Brocot tree).

• If $$r\geq s$$ and $$a_i = b_i$$ for all $$0\leq i\leq s$$, then the sought-after rational is $$q = [b_0;b_1,\ldots,b_r,1]$$ itself (it is an ancestor of $$p$$ in the Stern-Brocot tree).

Example: Suppose I want to find the rational with smallest denominator between $$1.728 = [1; 1, 2, 1, 2, 10, 1]$$ and $$1.729 = [1; 1, 2, 1, 2, 4, 2, 2, 1, 1, 1]$$: the algorithm in question shows that it's $$[1; 1, 2, 1, 2, 4, 1] = 102/59$$; and of course, this rational is also the rational with smallest denominator between itself and any of the two numbers I started with, which exemplifies the edge cases.

• In order to avoid pre-calculating the continued fractions, it may be useful to just descend the Stern-Brocot tree using "componendo-dividendo" which is the inequality $a/b < (a+c)/(b+d) < c/d$. So one starts with $0/1 < 1/0$ and iterates with this until the mid-point lies in the interval. (Assuming that the numbers are positive.) This can be made faster by using integer parts of ratios. Jun 12 at 13:26
• This also tells me that the solution is unique, in particular if there is always a $n/k \le n'/k' \le (n+1)/k$ with $k' \lt k$ Jun 12 at 23:06
• Series, The Geometry of Markoff Numbers shows how this relates to traversals of tessellations of the euclidean and hyperbolic planes. Jun 21 at 23:31