Rational-interval rounding of a counting output

Input. Public integers $N\ge 1$, even $M\ge 2$, and $0\le y<M$. The output is an integer $q$. All sums, factorials, comparisons and ceiling operations below use exact rational or integer arithmetic, charged as classical bit work under Classical bit-operation cost.

If $y=0$, return $q=0$. Otherwise initialize $r=4$. Compute $R_r=8^{2r+2}\mathrm{/}(2r+2)!$; while $N{R}_r\ge 1\mathrm{/}24$, increment $r$ by one and recompute $R_r$. At the first $r$ with $N{R}_r<1\mathrm{/}24$, set $D_r={\sum }_{k=1}^r\frac{2k{8}^{2k-1}}{(2k)!}\mathrm{.}$

Initialize $h=1$. Compute $S_h={\sum }_{k=0}^{h-1}\frac{(-1{)}^k}{2k+1},e_h=\frac{4}{2h+1},[a_h,b_h]=\frac{2y}{M}[4S_h-e_h,4S_h+e_h]\mathrm{.}$ These are the arctangent-series enclosures from Principal arctangent: derivative, integral, power series, and the Gregory–Leibniz series and The alternating series test: if $(b_k)$ is nonincreasing with $b_k\to 0$ then ${\sum }_k(-1{)}^k{b}_k$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_n$. Set $x_h=(a_h+b_h)\mathrm{/}2$ and ${\rho }_h=(b_h-a_h)\mathrm{/}2$. While either $[a_h,b_h]⊈[0,8]$ or $N{D}_r{\rho }_h\ge 1\mathrm{/}24-N{R}_r$, increment $h$ by one and recompute $S_h,e_h,a_h,b_h,x_h,{\rho }_h$.

For the first accepted $h$, compute $C_r(x_h)={\sum }_{k=0}^r\frac{(-1{)}^k{x}_h^{2k}}{(2k)!},E=D_r{\rho }_h+R_r,$ $u=\frac{N}{2}(1-C_r(x_h)-E),v=\frac{N}{2}(1-C_r(x_h)+E)\mathrm{.}$ Return $q=\lceil v-2\mathrm{/}3\rceil$, computing the rational ceiling by integer division. The termination and error guarantee are established in Terminating certified rounding for a counting estimate ↗.