Relative approximate counting with unknown marked count

Input. A Boolean predicate on $N=2^n\ge 1$ addresses with an integer $n\ge 0$, the fully declared controlled counting access model, and rational $0<ϵ\le 1$.

Set $\mathrm{\ell }=0$. Repeatedly increment $\mathrm{\ell }$, set $L=2^{\mathrm{\ell }}$, run a fresh Count$(f,L)$, and stop exactly when its label $y$ is nonzero or $L^2\ge 4N$. The test $y\mathrm{\ne }0$ is an exact finite label test. Initialize $m=0$ and $M=1$; repeatedly increment $m$ and double $M$ while $M<[20(22\mathrm{/}7{)}^2\mathrm{/}ϵ]L$, using exact rational comparison, so that $M=2^m$. Run a fresh Count$(f,M)$ and run Rational-interval rounding of a counting output on $(N,M,y)$ to output an integer within $2\mathrm{/}3$ of its exact algebraic count estimate, as proved by Terminating certified rounding for a counting estimate. The scale loop returns the least power of two meeting its rational threshold; all scales are powers of two and the multiplier grows as $1\mathrm{/}ϵ$ times $L$.