# How to compute next/previous representable rational number?

An (approximate) non-negative rational number representation is a pair of natural numbers each not greater than some fixed limit M (and of course denominator being non-zero).

With this condition there is finite number of representable rational numbers. This means that for each such number we can name previous and next number in the set (of course except for smallest 0 and largest 1). How to compute them?

In other words lets have a set of numbers

$$R(M)=\{\frac{p}{q} : p,q\in\mathbb{N},q\neq0,p\leq q\leq M\}$$

where $M\in\mathbb{N}_+$

and given number $\frac{p_1}{q_1}\in R(M)$.

I want to find numbers $\frac{p_S}{q_S}\in R(M)$ and $\frac{p_L}{q_L}\in R(M)$ (if they exist) such that

$$\frac{p_S}{q_S}<\frac{p_1}{q_1} \wedge \neg\exists_{\frac{p}{q}\in R(M)}\frac{p_S}{q_S}<\frac{p}{q}<\frac{p_1}{q_1}$$

and smilarly

$$\frac{p_L}{q_L}>\frac{p_1}{q_1} \wedge \neg\exists_{\frac{p}{q}\in R(M)}\frac{p_1}{q_1}<\frac{p}{q}<\frac{p_L}{q_L}$$

-
You can iterate over all the elements of $R(M)$, of which there are $O(M^2)$, replacing the closest predecessor/successor found so far whenever a closer one is found, and find the predecessor and successor that way. So this is more a question of complexity than feasibility, right? It's not hard to write an algorithm that iterates over denominators instead, and so takes $O(M)$ integer operations. Can one do substantially better? –  mjqxxxx May 17 '11 at 11:22
@mjqxxxx: Yes. A brute-force algorithm can be done easly but is not very useful due to time complexity. How would you do it iterating only over denominators? –  Adam Badura May 17 '11 at 11:42
The largest representable number in $R(M)$ would not be $1$, but $\frac{M}{1} = M$. –  Paŭlo Ebermann May 17 '11 at 12:47
@Paŭlo Ebermann: Good point. I corrected $R$ definition to limit it to $[0;1]$ range. –  Adam Badura May 17 '11 at 12:58

All this needs is a single modular inversion, with complexity $O(\log M \log \log M)$ (or something like that).

We are given $p/q$ in lowest terms, with $p, q \in \mathbb{N}$ and $q > 0$. We want the nearest neighbours of $p/q$, $a/b < p/q < c/d$, subject to $a,b,c,d \in \mathbb{N}$ and $c,d > 0$. Assume for the moment that $p < q$.

Consider $c/d$. It is the element after $p/q$ in the Farey sequence $F_n$, which means that $cq - dp = 1$. In particular, $dp+1 = 0 \pmod q$, i.e. $d = -1/p \pmod q$. So let

$r = 1/p \pmod q$

Now make $d$ as big as possible, subject to (i) $d = -r \pmod q$ and (ii) $d \leq n$. Then just put $c = (dp+1)/q$.

Similarly, to calculate $a/b$, make $b$ as big as possible subject to (i) $b = +r \pmod q$ and (ii) $b \leq n$. Then put $a = (bp-1)/q$.

An example Suppose $p/q = 28/61$ and $n=100$. Then the inverse of $28 \pmod{61}$ is $r=24$. So $d = 37 \pmod{61}$, and we can take $d=98$, with $c=(98.28+1)/61 = 45$. And $b = 24 \pmod{61}$, so we can take $b = 85$, with $a = (85.28-1)/61=39$. So we get:

$39/85 < 28/61 < 45/98$

We only have to modify this slightly to handle the case $p > q$: instead of computing the largest $d \leq n$ that satisfies the modulo requirement, we find the corresponding modulo requirement for $c$, and then look for the largest such $c \leq n$. You can fill in the details for yourself.

-
How do you know the time complexity is $O(\log M \log\log M)$? I assume that counting inverse of $p$ (mod $q$) is done by some already established algorithm. But than you still have to make $d$ as big as possible so how you do it? Trying all numbers down from $M$ leads to linear time complexity... –  Adam Badura May 17 '11 at 13:17
Look up "Extended Euclidean Algorithm" for the modular inversion. As for making $d$ as big as possible...do I really have to spell it out? OK: put $d = ([M/q] + 1)q - r. If d is too big, subtract q. – TonyK May 17 '11 at 13:24 Check out the next link: http://en.wikipedia.org/wiki/Farey_sequence . In general, Farey sequence is dealing exactly with that type of question. - A fine link. Thanks. Yet it does not (directly) provide an answer. And since it presents a method for computing next/previous number having two other I'm starting to think that there is no way to do it with only one. But maybe there is? – Adam Badura May 17 '11 at 10:43 As I mentioned in a closely related question, this has a very beautiful geometrical interpretation employing Pick's Area Theorem:$\rm\: a/b < c/d\:$are two adjacent terms in a Farey sequence iff the triangle$\rm T$with vertices$\rm (0,0), u = (b,a), v = (d,c)$contains no lattice points except for vertices. By Pick's formula this is true iff$\rm\ area\ T = $#interior_points$\ +\ 1/2\ $#boundary_points$\:-\ 1\ =\ 0 + 3/2 - 1 = 1/2\:.$But by basic analytic geometry$\rm\: area\ T\: =\: |det(u,v)|/2 = |ad-bc|/2\:.\:$Hence$\rm\:a/b,\:c/d\:$are meighbors in some Farey sequence iff$\rm\:|ad-bc| = 1\:.\:$Therefore the problem reduces to solving the linear Diophantine equation$\rm\:ax+by = 1\:.\:$As is well-known, such equations may be solved by employing the extended Euclidean algorithm, which is conveniently implemented by performing the Euclidean algorithm in parallel on an identity-augmented system of equations. For an example worked-out in detail see my post here. In fact it deserves to be much better known that Pick originally applied his area formula in a similar way to give a beautiful geometric proof of the Bezout linear representation of the gcd. - Given these two excellent uses of Picks theorem, I was wondering how much more could be done with it? (Maybe that would be a good question to ask?) – quanta May 17 '11 at 18:23 So far I have found algorithm iterating over denominators (inspired by mjqxxxx's comment). Thus it is of$O(M)$time complexity (however each iteration is short and simple). In Farey sequence for two consecutive fractions$\frac{p_1}{q_1}<\frac{p_L}{q_L}$it holds that$p_L q_1 - p_1 q_L=1$. Thus$p_L=\frac{p_1 q_L + 1}{q_1}$. We have$\frac{p_1}{q_1}$and$M$and we want to know$\frac{p_L}{q_L}$. Since$1\leq q_L\leq M$we can now simply iterate over all natural numbers in range$[1;M]$and for each see whether$\frac{p_1 q_L + 1}{q_1}$is a natural number. If so than we have the desired fraction$\frac{p_L}{q_L}$. It may happen that this will be solved for more than one value in that range. This means that depending on$M$the solution are different fractions. Thus of interest is the last (I think - I haven't prove that) value and it would be better to iterate from$M$to$1$rather than the other way. (Finding previous fraction can be done in similar way using$p_S=\frac{p_1 q_S – 1}{q_1}$.) It remains an open question whether indeed the largest$q_L$/$q_S$which solves the equation in natural numbers is the solution. Also this is still$O(M)\$ so maybe something faster can be found?

-