Time complexity for fraction-search-algorithm

[Aeren1564]

The algorithm described in https://cp-algorithms.com/others/stern_brocot_tree_farey_sequences.html#fraction-search-algorithm works in linear quadratic time in numerator+denominator, but the article claims that it is a "binary search algorithm".

[jakobkogler]

Did you understand the algorithm correctly? It is indeed logarithmic in n+m.
E.g.

>>> find(34, 53)
find(x=34, y=53, a=0, b=1, c=1, d=0)
find(x=34, y=53, a=0, b=1, c=1, d=1)
find(x=34, y=53, a=1, b=2, c=1, d=1)
find(x=34, y=53, a=1, b=2, c=2, d=3)
find(x=34, y=53, a=3, b=5, c=2, d=3)
find(x=34, y=53, a=5, b=8, c=2, d=3)
find(x=34, y=53, a=7, b=11, c=2, d=3)
find(x=34, y=53, a=7, b=11, c=9, d=14)
find(x=34, y=53, a=16, b=25, c=9, d=14)
find(x=34, y=53, a=25, b=39, c=9, d=14)
'LRLRRRLRR'

Or why do you think think that it is quadratic?

[adamant-pwn]

Hi all, Aeren is right that the algorithm is quadratic. First of all, proper search on the Stern-Brocot tree should compress the output in run-length encoding. So, if L or R is repeated $k$ times, the number $k$ should be found with binary search (or with floor function, if it's possible based on the target function), and the output should effectively be the continued fraction of $\frac{x}{y}$. Otherwise, the size of the output might reach $x+y$, e.g. when $x=1$ or $y=1$.

Another thing to note is that it returns strings like 'L' + find(...), which means that it copies the result every time before appending L or R to its beginning (so, it's in fact quadratic). Overall, we should fix the algorithm to better correspond to what is explained here.

[Aeren1564]

Did you understand the algorithm correctly? It is indeed logarithmic in n+m. E.g.

>>> find(34, 53)
find(x=34, y=53, a=0, b=1, c=1, d=0)
find(x=34, y=53, a=0, b=1, c=1, d=1)
find(x=34, y=53, a=1, b=2, c=1, d=1)
find(x=34, y=53, a=1, b=2, c=2, d=3)
find(x=34, y=53, a=3, b=5, c=2, d=3)
find(x=34, y=53, a=5, b=8, c=2, d=3)
find(x=34, y=53, a=7, b=11, c=2, d=3)
find(x=34, y=53, a=7, b=11, c=9, d=14)
find(x=34, y=53, a=16, b=25, c=9, d=14)
find(x=34, y=53, a=25, b=39, c=9, d=14)
'LRLRRRLRR'

Or why do you think think that it is quadratic?

It takes N calls to reach 1/N (1/1 -> 1/2 -> 1/3 -> 1/4 -> ... -> 1/N)

[jakobkogler]

@Aeren1564 My bad. I was completely wrong here.
I remember using a faster version in a contest once, and I was pretty sure that I copied it from here. But I guess I was mistaken.

We should fix that, and provide a faster version. Implementing it with binary search doesn't look too hard.

[adamant-pwn]

b19ce68: I rewrote the recursive code into iterative manner, so that it's $O(p+q)$ rather than $O((p+q)^2)$ now. I also added $O(\log(p+q))$ code that finds the compressed description of the path from root for a specific fraction $\frac{p}{q}$, and some comments on how one should use binary search to find coefficients in a more generic case. Keeping this open, as we still might need generic search function with predicates, but at least it shouldn't be considered a bug anymore.