6
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ I'd look at continued fraction algorithms $\endgroup$ Jun 11 at 15:41
  • $\begingroup$ 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”. $\endgroup$
    – Gro-Tsen
    Jun 11 at 18:09
  • 3
    $\begingroup$ 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. $\endgroup$
    – Gro-Tsen
    Jun 11 at 18:11
  • $\begingroup$ See also Exercises 4.5.3.39 and 4.5.3.40 in Knuth's Seminumerical Algorithms. $\endgroup$ Jun 30 at 17:16

1 Answer 1

9
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kapil
    Jun 12 at 13:26
  • $\begingroup$ 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$ $\endgroup$
    – afiori
    Jun 12 at 23:06
  • $\begingroup$ Series, The Geometry of Markoff Numbers shows how this relates to traversals of tessellations of the euclidean and hyperbolic planes. $\endgroup$
    – brainjam
    Jun 21 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.