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
\begin{equation}
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.
\end{equation}
Or


\begin{equation}
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.
\end{equation}


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



How can I efficiently find the "simplest" rational in an interval?
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<q$).
* 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](https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_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.


