= Integer logarithm
{title2=$\lfloor\log_b n\rfloor$}
For <integers> $b>1$ and $n>0$, the <integer logarithm> is the largest <nonnegative integer> $i$ such that $b^i\leq n$. Equivalently,
$$
b^i\leq n<b^{i+1},\qquad i=\lfloor\log_b n\rfloor.
$$
The equivalence follows from the monotonicity of <exponentiation> in its exponent and the definition of the <floor function>. For example, $3^4=81\leq100<243=3^5$, so the base-three <integer logarithm> of $100$ is $4$.
A multiplication loop maintains $p=b^i\leq n$ and accepts another factor $b$ while $pb\leq 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\leq L<i+2^{k+1}$. Accepting $2^k$ exactly when $i+2^k\leq 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\leq n\mathbin{\mathrm{DIV}}q$ before multiplying by $q$. <Integer division> makes this equivalent to $pq\leq n$ while preventing <integer overflow> in a rejected candidate.
Back to article page
