jk-jeon
commented
2 years ago Turns out to be possible.
For given $n$, suppose that we have found $y$ and $Q$ such that
$$ n = \left\lfloor \frac{yD}{2^{Q}} \right\rfloor. $$
Here we will choose $D=10^{8}$ for 9 or 10 digits $n$, $D=10^{6}$ for 7 or 8 digits $n$, and so on. Now, suppose $d$ is a divisor of $D$. Then it easily follows
$$ \left(\left\lfloor \frac{nd}{D} \right\rfloor \ \textrm{mod}\ d\right) = \left\lfloor \frac{(y\ \textrm{mod}\ 2^{Q})\cdot d}{2^{Q}} \right\rfloor $$
and
$$ \left(n\ \textrm{mod}\ \frac{D}{d}\right) = \left\lfloor \frac{(yd\ \textrm{mod}\ 2^{Q})\cdot(D/d)}{2^{Q}} \right\rfloor. $$
So for example, assuming $D=10^{8}$, to check if the last 8 digits of $n$ are all zero we just need to inspect the inequality
$$ (y\ \textrm{mod}\ 2^{Q}) \leq \frac{2^{Q}}{D}. $$
Similarly, to check if the last 6 digits of $n$ are all zero, we just need to inspect the inequality
$$ (yd\ \textrm{mod}\ 2^{Q}) = \left( (y\ \textrm{mod}\ 2^{Q})d\ \textrm{mod}\ 2^{Q}\right) < \frac{2^{Q}d}{D} $$
where $d=10^{2}$.
Simply, at each stage of iteration, to get the next $\eta$-digits we multiply $10^{\eta}$ to the remainder from the last stage. Hence, if the multiplication gives us zero after cutting the remainder bits, we immediately conclude that there is no nonzero digits left.
When spitting out decimal digits via jeaiii-style integer formatting, it is probably possible to do integer checks to figure out that all the remaining digits are zero. Then maybe we can spare yet more multiplications therefore get a better performance.