What's the quickest way to check if an interger is a perfect power?


by redjoker
Tags: check, interger, perfect, power, quickest
redjoker
redjoker is offline
#1
Oct13-08, 09:07 PM
P: 5
I want to write a program that checks whether a consumed positive integer, n, is a perfect power or not. What would be the most efficient implementation of that program? I can think of an obvious implementation (checking if all 0 < i <= n/2 are power roots of n), but I'm rusty on number theory so I'm not sure if there exists a better way. I wouldn't want to get into case analysis, but if the gains in efficiency are significant, I'd consider it.
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
JasonRox
JasonRox is offline
#2
Oct13-08, 09:50 PM
HW Helper
PF Gold
JasonRox's Avatar
P: 2,328
That's probably trickier than it sounds.

Is the number 36 considered a number of perfect power? Because that is 6^2 = 36.

That would make things very complicated.
redjoker
redjoker is offline
#3
Oct13-08, 10:04 PM
P: 5
Yes that's what I mean. If by complicated you mean slow, yeah you are right.

Ben Niehoff
Ben Niehoff is offline
#4
Oct13-08, 10:30 PM
Sci Advisor
P: 1,562

What's the quickest way to check if an interger is a perfect power?


This way should be fast:

Call the number N_0:

1. Find how many times 2 goes into N_0; say N_0 = 2^A * N_1, where N_1 is an integer which is not divisible by 2.

2. Find how many times 3 goes into N_1. Let N_2 = N_1 / 3^B. If B > 0 and A != B, then fail. If B = 0 or B = A, then continue.

3. Repeat with the i-th prime on N_i in the same fashion until either N_i is prime or 1.

This algorithm takes advantage of the fact that if N is a perfect power, then the prime factorization of N must be of the form

(abcd...)^k = a^k * b^k * c^k * d^k * ...

Note that at every step in the iteration, you need only continue testing divisibility up to sqrt(N_i), NOT N_i/2. Since each N_i is less then the previous one, the algorithm has a worst-case complexity of

O(sqrt(N))

when N is prime, and on average, does better than that.
CRGreathouse
CRGreathouse is offline
#5
Oct14-08, 12:25 AM
Sci Advisor
HW Helper
P: 3,680
A practical implementation to check if n is a perfect power (with exponent > 1):

1. For each small prime p, check how many times p goes into n. If the gcd of the exponents is 1, the number isn't a power with exponent > 1. (If 2^7 and 3^5 divide the number, gcd(7, 5) = 1 so it it's only a first power. If 2^12 and 7^4 divide the number, it may be a first, second, or fourth power.)

2. If you find a prime p where p^a divides n (but p^(a+1) does not) for a > 0, test if n is a kth power for each prime k dividing a. (If 2^14 but not 2^15 divides n, then test if n is a square or a 7th power.)

3. If you don't find a prime dividing the number, either try harder to find a factor (with ECM, perhaps) or trial divide up to the cube root of the number. If n has no factors below its cube root, it is a perfect power (exponent > 1) iff it is a square.


To check if a number is a k-th power, take the kth root of the number and see if it is an integer. A typical method of dealing with roundoff: take m = nearest_integer(pow(n + 0.5, 1.0/k)) and see if m^k is above n, below n, or equal to n. If equal, you're done (n is a kth power); if above or below, add or subtract one and see if the other number is on the opposite side. If m^k < n < (m+1)^k you know that n is not a kth power.


This method is faster than Ben's, with complexity O(n^(1/3)).
Hurkyl
Hurkyl is offline
#6
Oct14-08, 12:48 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
It seems more straightforward to just compute the square root of N, the cube root N, et cetera. There are only log(N)/log(2) possibilities. Combining the techniques would probably be even faster, but probably not asymptotically faster.
Ben Niehoff
Ben Niehoff is offline
#7
Oct14-08, 03:54 AM
Sci Advisor
P: 1,562
Quote Quote by CRGreathouse View Post
This method is faster than Ben's, with complexity O(n^(1/3)).
It's also far more correct, as my algorithm neglected the case where the prime factors of N might have different powers, but still have a GCD greater than 1.
Ben Niehoff
Ben Niehoff is offline
#8
Oct14-08, 04:02 AM
Sci Advisor
P: 1,562
Quote Quote by Hurkyl View Post
It seems more straightforward to just compute the square root of N, the cube root N, et cetera. There are only log(N)/log(2) possibilities. Combining the techniques would probably be even faster, but probably not asymptotically faster.
The catch is that computing the Nth root of a number is expensive. By carefully designing the algorithm, one can do everything with integers and not have to compute roots at all; thus avoiding both the expense and roundoff errors of floating point operations.
Hurkyl
Hurkyl is offline
#9
Oct14-08, 04:41 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
Quote Quote by Ben Niehoff View Post
The catch is that computing the Nth root of a number is expensive. By carefully designing the algorithm, one can do everything with integers and not have to compute roots at all; thus avoiding both the expense and roundoff errors of floating point operations.
Nevertheless, log(N) is much smaller than N^(1/3), unless N is so small that this whole discussion is moot. And besides, root extraction isn't as bad as you make it sound, especially if you're looking for integer roots. Newton's method converges quite quickly, and can be used modulo a sufficiently large power of 2 (i.e. in the 2-adic numbers) rather than working in the reals.

For what it's worth, GMP computes n-th roots.
CRGreathouse
CRGreathouse is offline
#10
Oct14-08, 08:51 AM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by Hurkyl View Post
It seems more straightforward to just compute the square root of N, the cube root N, et cetera. There are only log(N)/log(2) possibilities. Combining the techniques would probably be even faster, but probably not asymptotically faster.
Oh yes, this is asymptotically much faster -- O(log^3 n) rather than O(n^(1/3)), assuming you use Newton's method for roots. You can even improve it to O(M(log n) log n/log log n) by taking only prime roots, which is about O(log^2 n) using S-S multiplication.

But if the numbers are large, I'd expect more care would be given to this problem then copying out pseudocode from a forum. You'd want to check the results modulo several small primes using reciprocity results; you'd want to use Bernstein's almost-linear prime power detection routine; you'd want a good pseudoprimality routine; you'd want careful meet-in-the-middle coding to determine how far primes are checked vs. how far roots are taken.

Quote Quote by Hurkyl View Post
For what it's worth, GMP computes n-th roots.
Or you'd want GMP.
mathman
mathman is offline
#11
Oct14-08, 03:47 PM
Sci Advisor
P: 5,935
Quote Quote by redjoker View Post
I want to write a program that checks whether a consumed positive integer, n, is a perfect power or not. What would be the most efficient implementation of that program? I can think of an obvious implementation (checking if all 0 < i <= n/2 are power roots of n), but I'm rusty on number theory so I'm not sure if there exists a better way. I wouldn't want to get into case analysis, but if the gains in efficiency are significant, I'd consider it.
If you expect to do this for many integers, it might pay to generate a sorted list of perfect powers up to the largest number you could consider.

Then use a simple search algorithm to see if a given number is on the list.


Register to reply

Related Discussions
Quickest Way to Learn QM Academic Guidance 10
Power check and help Introductory Physics Homework 3
Power Question: Just Check My Work! Introductory Physics Homework 15
Negative numbers to non-interger powers General Math 11
Quickest Question Ever. Introductory Physics Homework 15