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

Use repeated squaring, including index zero:The loop invariant is $b_2[j]=b^{2^j}$ for $0\le j\le \mathrm{top}$, with $b_2[j]\le n$ for every stored entry except possibly the initial entry when $b>n$. Squaring $b^{2^j}$ gives $b^{2^{j+1}}$, proving preservation. The first failed guard identifies the first larger power outside the range. If $b>n$, no power with $k\ge 1$ needs storing.

Index zero is deliberately included. The original paper asks for indices $k\ge 1$ but then claims that their products represent every allowable power. Taken without $b_2[0]=b$, that claim fails for odd exponents, since every available exponent would be even. The extra initialized entry makes the intended binary expansion argument valid without changing the requested entries.

Let $M$ be the largest representable positive integer. The worst case is $b=2$, requiring indices through $\lfloor {\log }_2\lfloor {\log }_{2}M\rfloor \rfloor$. Thus enough = 5 for signed 32-bit integers, or 6 for signed 64-bit integers, suffices for stored powers that fit; a larger convenient constant is harmless. This counts slots starting at zero and does not reserve a slot for an out-of-range sentinel. The multiplication in the guard can still suffer integer overflow, independently of this array capacity bound.