# Smart way to calculate floor(log(x))?

I thought of an algorithm that involves $\lfloor \log_{b} x \rfloor$ and am trying to determine its computational complexity. At first glance my algorithm looks polynomial, but I read that my algorithm may be pseudo-polynomial since I have to take the size of the input into account. It mostly comes down to the floored logarithm. I couldn't find much on the complexity of the log function.

Actually calculating $\lfloor \log_{b} x \rfloor$ by discarding digits from a logarithm seems wasteful. I found that $\lfloor \log_{b} x \rfloor$ is also known as 'finding the least-significant non-zero digit' in the representation of $x$. This is at most linear, but only if we already have a representation of the number in the specified base $b$.

So my question is: given that $1 \le x$, is there a smarter way to calculate $\lfloor \log_{b} x \rfloor$ for any integer base $b$, and what is its computational complexity (in terms of the size of $x$)?

• For $x>1$, a simple method is to repeat $x:=\lfloor x/b\rfloor$ until the result is zero – Hagen von Eitzen Jan 26 '16 at 16:35

Supposing $b > 1$ and $x \geq 1$, the pseudocode algorithm
L := 0

returns $\lfloor \log_b x \rfloor$. (CS aside: If $b$ is an integer, this gives an exact result when all variables have type int. If the variables have type, e.g., float, likely this algorithm can return rounding errors.) For any $x$ the while loop is run $\lfloor \log_b x \rfloor + 1$ times, so this algorithm has complexity $O(\log x)$ in $x$.