patternMinor
How does one find out whether $N = a^b$ for some integer $a$ and $b$?
Viewed 0 times
howandonefordoesfindsomewhetheroutinteger
Problem
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 it is not a perfect power if it is not expressible 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. Are there efficient algorithms?
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. Are there efficient algorithms?
Solution
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$:
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.
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.
Context
StackExchange Computer Science Q#48033, answer score: 6
Revisions (0)
No revisions yet.