Integer root extracting
Hans Aberg
haberg-1 at telia.com
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