It is simple to decide powers of 2 in $O(n)$ time because it's just "0-bit Unary" after bit-1. (eg. $1000$ is a power of 2 in binary).

I haven't found many other trivial powers of $K$ that can be decided in polynomial-time with the binary-length of the input.


Can we decide if a number is a power of any given $K$ in polynomial-time and in a practical amount of time?

Something not naive such as keep dividing $N$ by $K$ until you reach the smallest value $2$ for deciding a power of 2.

  • $\begingroup$ This also allows a special case of factorization in $P$. Just simply delete the 0-bit one by one at a time until you reach $1$. Each iteration is a factor of a power of $2$. Use binary factors, not integer factors. Integer factors would be slower! $\endgroup$ – Travis Wells Jul 13 '20 at 23:33
  • 1
    $\begingroup$ Yes. Use binary search on the value of the exponent. See cs.stackexchange.com/q/48033/755. $\endgroup$ – D.W. Jul 13 '20 at 23:36
  • $\begingroup$ @D.W. Seems like a $O(n log n)$ algorithm (integer factorization of powers of 2). If I could guess, I'm just an amateur tinkering in college algebra and lots of python practice. $\endgroup$ – Travis Wells Jul 13 '20 at 23:37
  • $\begingroup$ I don't understand your problem. You are given a number N and number K and want to check whether N is a power of K? Why no just divide N by K repeatedly? It will be polynomial in the length of N. $\endgroup$ – user114966 Jul 13 '20 at 23:49
  • 1
    $\begingroup$ Instead of dividing by $K$ each time, I would compute $K, K^2, K^{2^2},K^{2^3},...$ and divide by the largest such that is not larger than $N$. Repeat the same procedure with the resulting quotient. It would take about $\log_2(\log_K(N))$ divisions, same number of multiplications (squaring). Then you can count each of these big int operations how fast they are in bit operations. $\endgroup$ – plop Jul 14 '20 at 1:26

Your Answer

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

Browse other questions tagged or ask your own question.