Bit cost of phase-sample rational reconstruction

Let $q_j$ be the convergent denominators, with $q_0=1$ and $q_1\ge 1$. The recurrence in [F1] gives $q_{j+2}\ge q_{j+1}+q_j\ge 2q_j$ whenever both indices exist. Since the terminal denominator is at most $Q$, every two quotient steps at least double a positive denominator, so the number of Euclidean divisions is at most $2L+O(1)=O(L)$.

The reduced denominator of $y\mathrm{/}Q$ is at most $Q$, so the recurrence in [F1] makes each convergent denominator at most its terminal denominator. Since $0\le y\mathrm{/}Q<1$, the normalized expansion starts with $a_0=0$; its initial convergents satisfy $0\le p_0\le q_0$ and $0\le p_1\le q_1$, and the recurrence with positive later digits preserves $0\le p_j\le q_j$. Thus all convergent numerators and denominators have $O(L)$ bits. By the division algorithm in [F1], binary long division of two such integers can be performed by at most $O(L)$ compare/subtract scans of at most $O(L)$ bits, hence $O(L^2)$ multitape transitions under [F2].

Updating a convergent numerator and denominator by [F1] uses a constant number of products and sums on $O(L)$-bit integers, hence $O(L^2)$ transitions per update. Each convergent candidate also requires a constant number of products $y{q}_j$ and $p_{j}Q$, an absolute difference, a doubling, and a comparison with $q_j$. Schoolbook multiplication and these scans each cost $O(L^2)$ transitions. There are $O(L)$ candidates by step 1.1, so total comparison work is $O(L^3)$; writing the selected numerator and denominator costs only $O(L)$.

The routine normalizes the rational by exact Euclidean divisions and applies only the integer test from [F1]; all work is covered by the above bounds. Hence its deterministic multitape bit cost is $O(L^3)$ and it performs no floating-point comparison.