I erred in a previous post in saying my algorithm to determine the ordinal N of a rational a/b ran in O(log(a)+log(b)+1) time. There are counterexamples. It genuinely runs in O(1+logN) time but that's a weaker bound. The runtime is a bit like the runtime for a hamstrung variant of the "binary GCD" algorithm on (a,b) but the problem is if a<<b and a,b have opposite parities, then your grandparent in the Calkin-WIlf tree is (a, b-2a) which is pathetically slow progress toward the tree-root. However, it seems to me we can speed things up in this case by doing many steps at once. After 2M to-parent steps which automatically all will be in the same "direction" you go directly to (a, b-2Ma) and we can choose M=floor((b-a)/(2a)) so that this is a big reduction. That makes the speed more like the Euclidean GCD algorithm. Then, the runtime bounds I was erroneously claiming, become true again... provided you output N's binary expansion in a "runlength encoded" data-compressed format instead of straight binary. -- Warren D. Smith http://RangeVoting.org  <-- add your endorsement (by clicking "endorse" as 1st step)