= Solution
Store a second <array> `weight` with `weight[k] = 2^k`. Descending through the <binary digits> of the answer gives this <greedy algorithm>:
``
PROCEDURE FastLog(b, n: INTEGER): INTEGER;
VAR b2, weight: ARRAY enough OF INTEGER;
top, k, i, p: INTEGER;
BEGIN
b2[0] := b; weight[0] := 1; top := 0;
WHILE b2[top]*b2[top] <= n DO
b2[top+1] := b2[top]*b2[top];
weight[top+1] := weight[top]+weight[top];
top := top+1
END;
i := 0; p := 1; k := top;
WHILE k >= 0 DO
IF p*b2[k] <= n THEN
p := p*b2[k]; i := i+weight[k]
END;
k := k-1
END;
RETURN i
END FastLog;
``
For the second loop, write $L=\lfloor\log_b n\rfloor$. Immediately before processing $k$, its <loop invariant> is
$$
p=b^i\leq n,\qquad i\leq L<i+2^{k+1}.
$$
Initially the failed squaring guard gives $L<2^{\mathrm{top}+1}$; this also holds when $b>n$, since then $L=0$. The test succeeds exactly when $i+2^k\leq L$. If successful, adding $2^k$ selects that <binary digit>; otherwise the upper bound tightens to $L<i+2^k$. Either way the invariant holds for the next smaller $k$. At $k=-1$, $i\leq L<i+1$, so \b[`i = L`].
There are $O(1+\log(1+\log_b n))$ squarings and descending tests. For fixed $b$, this is \b[$O(1+\log\log n)$ arithmetic operations], hence logarithmic in the <bit length> of $n$, and also within the weaker $O(\log n)$ bound. This counts arithmetic operations on <integers> as unit cost; <bit complexity> would also charge for the growing operands. No division is used.
Back to article page
