5
$\begingroup$

I was trying to find out how to find whether $N$ is a perfect power or not for some $a$ and $b$ (so the algorithm should discover that its not a perfect power if its not expressable in the form $a^b$).

My intuition tells me that for every value of the exponent $b$ we can binary search $a$ in the set $\{ 1,...,N-1 \}$. However, what I am not convinced yet is that this algorithm won't run forever, i.e. that we won't try new values of $b$ forever. Also, if someone has any comments on the correctness of the algorithm I suggested it would be greatly appreciated.

$\endgroup$
4
4
$\begingroup$

Yes, your approach is a good one. The only thing you missed is that there's a simple upper bound $b \le \lg N$.

Do you see why? It's easier to see why if you state more carefully the problem you are trying to solve. You are asking whether there exist $a,b \in \mathbb{N}$ such that $a \ge 2$, $b \ge 2$, and $a^b=N$. Taking logs of both sides, we get $b \lg a = \lg N$. From the fact that $a \ge 2$, we see $\lg a \ge 1$, so $b = (\lg N)/(\lg a) \le \lg N$.

Therefore, here is a simple algorithm:

  • For $b=2,3,\dots,\lg N$:

    • Use binary search to search for $a \in \mathbb{N}$ such that $a^b=N$.

Each iteration of the loop will take $O(\lg N)$ time (the time for a binary search over at most $N$ possibilities), and you do $\lg N$ iterations of the loop, so the total running time $O((\lg N)^2)$.

In particular, yes, this will always terminate. You don't need to keep trying new values for $b$ forever, since we know that $b$ is an integer and is no larger than $\lg N$.

The running time of the algorithm can be improved a bit by replacing the binary search with a faster algorithm to compute $\sqrt[b]{N}$; for instance, you could use Newton's method. But the basic method above is already very efficient.


You might be tempted to iterate over all possible values of $a$, and then do a binary search for $b$. Don't do that; there are $\Theta(\sqrt{N})$ possible values of $a$, so this will be unavoidably slow.

Instead, a better approach is to iterate over all possible values of $b$, and then do a binary search for a matching $a$. This is much faster, as it needs only $\Theta(\lg N)$ binary searches rather than $\Theta(\sqrt{N})$ of them.

One person mentioned factoring $N$. This is much slower. Our best algorithms for factoring run in subexponential time; they are much slower than the $\Theta((\lg N)^2)$ running time of the algorithm above.

$\endgroup$
0
$\begingroup$

In addition to what @templatetypedef described, assuming we are talking about natural numbers, $a > 1$, and $b > 1$ we can make the following considerations:

  • The greatest number $a$ we have to consider is $sqrt(N)$, being that $sqrt(N)^2 = N$, so $a <= sqrt(N)$.
  • From the numbers we got in the previous point we can consider only half of them; even numbers if $N mod 2 = 0$, odd if $N mod 2 = 1$
  • The bigger $a$ is, the smaller $b$.

So, summing it up, you can follow the algorithm suggested by @templatetypedef while keeping in mind the lower/upper limits of $a$ and $b$, and avoiding odd/even numbers depending on $N$. If you need the greates $a$ possible you just start with the greatest $a$ such that $a <= sqrt(N)$. If you need the smallest you can start with $a = 2$.

$\endgroup$
2
  • 1
    $\begingroup$ This is not a good approach. It is far, far slower: its running time is $\Theta(N^{1/2})$, which is exoonentially slower than the strategy listed in the question. See my answer: cs.stackexchange.com/a/48060/755 $\endgroup$ – D.W. Oct 9 '15 at 16:27
  • $\begingroup$ You're right actually. The linear approach is not so efficient. Nevertheless, by using the considerations on the possible values of $a$ given in here with your consideration on the possible values of $b$ and the binary search on the possible values of $a$ it should be a bit faster, even though in terms of complexity it remains $O((lg N)^2)$. $\endgroup$ – Gentian Kasa Oct 9 '15 at 16:52

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.