= Solution
Use <repeated squaring>, including index zero:
``
b2[0] := b; top := 0;
WHILE b2[top]*b2[top] <= n DO
b2[top+1] := b2[top]*b2[top];
top := top+1
END;
``
The <loop invariant> is $b_2[j]=b^{2^j}$ for $0\leq j\leq\mathrm{top}$, with $b_2[j]\leq 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\geq1$ needs storing.
\b[Index zero is deliberately included.] The original paper asks for indices $k\geq1$ 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 \b[`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.
Back to article page
