2
$\begingroup$

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$)?

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

Supposing $b > 1$ and $x \geq 1$, the pseudocode algorithm

L := 0
while x >= b do
    L := L + 1
    x := x / b
end do
return L

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.