Integer root extracting
Torbjorn Granlund
tg at gmplib.org
Fri Sep 3 12:27:30 CEST 2010
Hans Aberg <haberg-1 at telia.com> writes:
GMP has a function mpz_perfect_power_p() that for given integer a
tells if a = x^y is solvable in integers x, y with y > 1. But I need
to find the largest y for which this is true (and also finding x). One
way to do this is to prime factor a and take the gcd of the exponents,
but is there a faster method?
Completely factoring a is of course not always possible.
A more tractable algorithm is the following:
for y = floor(log(a)/log(2)) to 2 by -1
If a^(1/y) is an integer, return y
The starting value is the largest power y for which a^(1/y) >= 2.
Testing if a^(1/y) can be done efficienty by computing mod some small
numbers; thus most non-solutions can be quickly rejected.
--
Torbjörn
More information about the gmp-discuss
mailing list