Finding parents in the Farey tree
The Farey tree crops up in the Mandelbrot set, a nice introduction can be found in The Mandelbrot Set and The Farey Tree by Robert L. Devaney. The tree operates on rational numbers by Farey addition, and can be defined recursively starting from (01,11) with an operation acting on neighbouring numbers:
ab⊕cd=a+cb+d
Section 6 of Devaney's paper begins
... Suppose 0<ab<cd<1 are the Farey parents of pq. ...
In practice it would be nice to be able to compute these Farey parents given pq. One approach is to perform a search through the tree, starting with bounds at 0 and 1, finding the Farey sum of the bounds and adjusting the bounds at each stage to keep the target fraction within them, stopping when it is reached. Unfortunately this has terrible asymptotic complexity, for example finding the Farey parents of 1100 in this way would step through 12,13,14,…198 before finding the parents (01,199).
Fortunately there is a better way suggested by Siddharth Prasad on math.stackexchange.com: using the extended Euclidean algorithm to solve for x and y:
qx+py=gcd
Then one parent is -\frac{x}{y} and the other can be found by undoing the Farey addition. For example, to find the parents of \frac{3}{100}:
q | r | s | t |
100 | 1 | 0 | |
3 | 0 | 1 | |
33 | 1 | 1 | -33 |
3 | 0 |
which gives one parent \frac{1}{33}, and by Farey addition the other parent is \frac{2}{67}.
The Euclidean algorithm has complexity O(\log q), which is a vast improvement over the naive search O(q).