Integer root extracting
Paul Zimmermann
Paul.Zimmermann at loria.fr
Fri Sep 3 15:39:36 CEST 2010
> From: Torbjorn Granlund <tg at gmplib.org>
> Date: Fri, 03 Sep 2010 12:27:30 +0200
>
> 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
you can restrict to prime exponent y. See Algorithm IsPower page 29 of [1],
and the comment just below.
Paul Zimmermann
[1] Modern Computer Arithmetic, Richard Brent and Paul Zimmermann,
version 0.5.3, August 2010, http://www.loria.fr/~zimmerma/mca/mca-cup-0.5.3.pdf.
More information about the gmp-discuss
mailing list