Guessing a rational number

 An algorithm puzzle after a long time.

I am thinking of a rational number $r$: $$\begin{aligned}&r = \frac{p}{q} \\& 0 \leq \frac{p}{q} \leq 1\\& \gcd(p,q) = 1\end{aligned}$$ 

Your goal is to guess $r$. At each step, you guess a rational number $g$ and I tell you whether $r > g, r = g$ or $r < g$. 

Can you guess $r$ in polynomial in $\log q$ guesses?

.

.

.

.

.

This is actually a math problem..

The main idea is to work with the simple canonical continued fraction representations of the rationals. We guess each "digit" of the continued fraction representation: $$r = [a_0; a_1, \dots, a_n] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\dots}}}$$

It can be shown the each digit $a_k$ is $O(q)$ and that the number of "digits" $n$ is $O(\log q)$, as the representation basically comes out of the extended euclidean algorithm for finding the $\gcd$ of $p$ and $q$. 

The guessing of each digit turns out to be binary search like and so we ultimately get an algorithm that makes $O(\log^2 q)$ guesses.

We are motivated by the following theorem (which we won't prove here):

$\textbf{Theorem:}$ Let $s = [a_0; a_1, \dots, a_n]$ and $t = [b_0; b_1, \dots, b_m]$ be canonical representations (so $a_n \neq 1$ and $b_m \neq 1$). Let $k$ be the first position where $s$ and $t$ differ, i.e $a_k \neq b_k$ and $a_i = b_i \forall i < k$. Then we have the following

$$\text{sign}(s-t) = (-1)^k \text{sign}(a_k - b_k)$$ 

where $$\text{sign}(x) = \begin{cases} 1 & x > 0 \\ 0 & x = 0 \\ -1 & x < 0 \end{cases}$$  

What this means is that to compare two continued fractions, it is enough to compare the "digits" at the first position they differ.

For eg $\frac{3}{2} = [1; 2]$ and $\frac{5}{4} = [1;4]$ and we have that $ \frac{3}{2} > \frac{5}{4}$, because they differ at $k=1$, and $2 < 4$ (so we flip the comparison because of the $(-1)^k$ term).

We also have the following (which we will actually use):

$\textbf{Observation:}$ Suppose $s = [a_0; a_1, \dots, a_n]$.  Now for $0 \leq m \leq n$, with a slight abuse of notation, we see that $s = [a_0; a_1, \dots, a_m + \epsilon]$ where $0 \le \epsilon \le 1$ and looking at it as a function of $\epsilon$, 

1) $s$ lies between $[a_0; a_1, \dots, a_m]$ and $[a_0; a_1, \dots, a_m + 1]$ (but could be equal to one of them).

2) if $b \neq a_m$, then $s$ does not lie between $[a_0; a_1, \dots, a_{m-1}, b]$ and $[a_0; a_1, \dots, a_{m-1}, b+1]$ (but could be equal to one of them).

This gives rise to the following algorithm.

$\textbf{Algorithm:}$

To guess $a_0$, do a binary search, comparing $r$ with $[x+1]$ and $[x]$. We vary $x$ in the standard binary search fashion. If $r$ lies in between them, then we have $a_0 = x$. If $r$ is strictly in-between, then $r$ has more digits.

Once we have $a_0$, to guess $a_1$, compare $r$ with $[a_0; x]$ and $[a_0; x+1]$. If $r$ is in-between, then $a_1 = x$, and if $r$ is strictly in-between, then $r$ has more digits. We vary $x$ in a  binary search way, but keeping in the mind increasing $x$ decreases the value of the fraction.

Once we have $a_0, a_1$, we compare with $[a_0; a_1, x]$ and $[a_0; a_1, x+1]$ and so on computing the rest of the $a_k$, keeping in mind the $(-1)^k$ factor in the above theorem.