Integer root extracting

Hans Aberg haberg-1 at
Fri Sep 3 15:13:59 CEST 2010

On 3 Sep 2010, at 12:27, Torbjorn Granlund wrote:

> 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.

I need to extract the root as well, so one can apply mpz_root()  
iteratively for the primes 2, 3, ..., p, as long as p <= log_2 a,  
though its value will only be used if the computation is exact.

More information about the gmp-discuss mailing list