Bit cost of exact known-count iteration selection

For $t>0$, $P(m):t{m}^2\ge N$ is monotone on nonnegative integers by [F9], and its least positive true index is $K=\lceil \sqrt{N\mathrm{/}t}\rceil$ by [F2]–[F3]. The doubling loop starts with false endpoint $\mathrm{l}\mathrm{o}=0$ and doubles $\mathrm{h}\mathrm{i}$ until $P(\mathrm{h}\mathrm{i})$ is true; it terminates because powers of two are unbounded. If $K=1$ it stops immediately. If $K>1$, the first true power of two satisfies $K\le \mathrm{h}\mathrm{i}<2K$, and the preceding power $\mathrm{l}\mathrm{o}=\mathrm{h}\mathrm{i}\mathrm{/}2$ is false. Upper-midpoint binary search preserves the false/true invariant and reduces each interval of width $d>1$ to width at most $\lceil d\mathrm{/}2\rceil$, so it reaches width one after $O(\log (K+1))$ evaluations and returns the least positive true index $K$. Since $K\le \lceil \sqrt{N}\rceil$, the endpoints have $O(n)$ bits for $n\ge 1$.

Put $a=t\mathrm{/}N$ and $\theta =\arcsin \sqrt{a}$. Then $q=1-2a=\cos (2\theta )$ by [F4]–[F5]. The recurrence has base values $T_0=\cos 0=1$ and $T_1=\cos (2\theta )=q$. By [F6], $\cos (2(m+1)\theta )+\cos (2(m-1)\theta )=2\cos (2\theta )\cos (2m\theta ),$ so induction in the recurrence gives $T_m(q)=\cos (2m\theta )$ for every computed index. Therefore $p_k=(1-\cos ((4k+2)\theta ))\mathrm{/}2={\sin }^2((2k+1)\theta )$, and the rational list in [F1] is the actual integer-iterate success list.

Write $u=N-2t$, so $q=u\mathrm{/}N$, and define $A_m=N^m{T}_m(q)$. Then $A_0=1$, $A_1=u$, and the recurrence gives $A_{m+1}=2u{A}_m-N^2{A}_{m-1},$ so each $A_m$ is an integer. By step 1.2 and [F8], $\mathrm{\mid }{A}_m\mathrm{\mid }\le N^m$. Thus for $n\ge 1$ and $m\le 2K+1$, both numerator $A_m$ and denominator $N^m$ have $O(Kn)$ bits. For $n=0$, $N=t=1$, $K=1$, and all recurrence values have constant bit length.

At recurrence index $m$, multiplying the $O(mn)$-bit integer $A_m$ by the $O(n)$-bit integer $u$ costs $O(m{n}^2)$ schoolbook bit operations; multiplication by $N^2$ is a binary shift, and addition costs $O(mn)$. Summing over $m\le 2K$ gives $O(K^2{n}^2)$. Each predicate evaluation in step 1.1 uses $O(n)$-bit operands and schoolbook arithmetic, hence $O(n^2)$ bit operations; the $O(\log (K+1))$ evaluations cost $O(n^2\log (K+1))\subseteq O(K^2{n}^2)$.

For odd $m=2k+1$, write $p_k=(N^m-A_m)\mathrm{/}(2N^m)$. Advancing from $k-1$ to $k$ scales the previous running-best numerator by $N^2$ to put it over the new denominator, then compares the two integers and updates only on strict increase. Each comparison costs $O(Kn)$ bit operations by step 2.1, and there are $K+1$ candidates, so all comparisons cost $O(K^{2}n)$, within step 3.1's bound. Strict updates retain the least $k$ in a tie.

If $t=1$, then $\sqrt{N}\le K=\lceil \sqrt{N}\rceil \le \sqrt{N}+1\le 2\sqrt{N}$, so $K=\mathrm{\Theta }(2^{n\mathrm{/}2})$. The preprocessing bound can therefore be exponential in $n$, and it supplies no polynomial-time conclusion from the query bound.

If $n=0$, necessarily $N=t=1$, so $K=1$ and the direct selection branch and finite recurrence take constant work, as stated.