= Solution
Keep both the exponent and its power. This <Oberon> procedure uses only the permitted arithmetic:
``
PROCEDURE IntLog(b, n: INTEGER): INTEGER;
VAR i, p: INTEGER;
BEGIN
i := 0; p := 1;
WHILE p*b <= n DO
p := p*b; i := i+1
END;
RETURN i
END IntLog;
``
The <loop invariant> is $i\geq0$ and $p=b^i\leq n$. It holds initially because $n>0$. A successful guard permits the next power, and the two assignments preserve the relation between $p$ and $i$. At exit, $p\leq n<pb$, which is exactly part (a). Each iteration increases $i$, and only finitely many powers of $b\geq2$ are at most $n$, proving <algorithm termination>. \b[The returned value is $\lfloor\log_b n\rfloor$.] Its <running time> is $\Theta(1+\log_b n)$ arithmetic operations; <integer overflow> is deferred to part (e).
Back to article page
