 Integer logarithm

For integers $b>1$ and $n>0$, the integer logarithm is the largest nonnegative integer $i$ such that $b^i\le n$. Equivalently,The equivalence follows from the monotonicity of exponentiation in its exponent and the definition of the floor function. For example, $3^4=81\le 100<243=3^5$, so the base-three integer logarithm of $100$ is $4$.

A multiplication loop maintains $p=b^i\le n$ and accepts another factor $b$ while $pb\le n$. Repeated squaring makes the search faster: precompute $b^{2^k}$ starting at $k=0$, and consider these factors in decreasing $k$. Include a factor when the accumulated product remains at most $n$. If $L=\lfloor {\log }_{b}n\rfloor$, the loop invariant before considering $k$ is $i\le L<i+2^{k+1}$. Accepting $2^k$ exactly when $i+2^k\le L$ halves that uncertainty, proving the greedy algorithm returns $L$. This takes $O(1+\log (1+{\log }_{b}n))$ arithmetic operations; it is not the same claim as this bound on bit complexity.

For positive operands in bounded integer arithmetic, test $p\le n\mathrm{DIV}q$ before multiplying by $q$. Integer division makes this equivalent to $pq\le n$ while preventing integer overflow in a rejected candidate.