Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 1 / e

Let $M$ be the maximum positive machine integer. A positive product $xy$ suffers integer overflow when $x>M\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\times 10^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\ge 2^{30}$.

For positive operands, integer division gives the exact equivalence $xy\le n⟺x\le n\mathrm{DIV}y$. Therefore replace the three guards respectively byand perform each multiplication only after its guard succeeds. Every accepted product is then at most $n\le M$. With these guarded products and sufficient table capacity, the algorithms work throughout $2\le b\le M$, $1\le n\le M$. The stored exponents and weights also fit in those machine ranges. Checking for overflow after multiplying would be too late.