= Solution
Let $M$ be the maximum positive machine <integer>. A positive product $xy$ suffers <integer overflow> when $x>M\mathbin{\mathrm{DIV}}y$. The vulnerable expressions are `p*b` in part (b), `b2[top]*b2[top]` in the table guard, and `p*b2[k]` in the descending search. Even a rejected candidate must be evaluated before its comparison with $n$.
The table guard becomes dangerous as soon as its current entry exceeds $\sqrt M$: approximately $46340$ for signed 32-bit <integers>, or $3.04\times10^9$ for signed 64-bit <integers>. These are thresholds for the intermediate power, not for $n$ alone. For example, with 32-bit arithmetic, $b=2$ and $n=65536$ reach the stored power $65536$ and then try its overflowing square $2^{32}$. If $b>46340$, even the initial square may overflow for a tiny $n$. In part (b), the final test can overflow when the next power above $n$ exceeds $M$; at $b=2$, this already happens for $n\geq2^{30}$.
For positive operands, <integer division> gives the exact equivalence $xy\leq n\iff x\leq n\mathbin{\mathrm{DIV}}y$. Therefore replace the three guards respectively by
``
p <= n DIV b
b2[top] <= n DIV b2[top]
p <= n DIV b2[k]
``
and perform each multiplication only after its guard succeeds. Every accepted product is then at most $n\leq M$. \b[With these guarded products and sufficient table capacity, the algorithms work throughout $2\leq b\leq M$, $1\leq n\leq M$.] The stored exponents and weights also fit in those machine ranges. Checking for overflow after multiplying would be too late.
Back to article page
