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.

Seminumerical Algorithms. $\endgroup$