A perfect power, and then?
tg at gmplib.org
Tue Oct 23 22:50:24 CEST 2012
nisse at lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund <tg at gmplib.org> writes:
> How should we solve this? It is tempting to let mpz_perfect_power_p
> return p, but unfortunately it has type 'int' which might be too small.
Which type would be right? mp_bitcnt_t?
Yes, or mp_exp_t.
> Any suggestions for a new function interface?
mp_bitcnt_t mpz_perfect_power_p (mpz_t x);
is mostly right. If x is a perfect power, return an exponent > 1, otherwise
A disadvantage is that this is an incompatible change.
1. Should it be required to return the *largest* exponent?
I would hesitate to pin that down. The current mpn/generic/perfpow.c
finds the largest exponent if it can factor the number, else the
2. What to return for inputs 0, and 1 and -1? They're perfect powers
(according to the docs), but which exponent should be returned?
(Here, "the largest one" is an impractical answer).
Perhaps 1 is the least silly answer.
3. Do all reasonable algorithms compute the root?
The current perfpow.c algorithm doesn't, at least not when is can factor
(The best algorithm I'm aware of would first try to exclude some
non-roots and exclude some potential exponents, and then compute the
root of the odd part of x mod a suitable power of two, and finally
check if that root is correct. So in the case that the argument is a
perfect power, it will at most take a shift to produce the root as
We use Bernstein's "Detecting Perfect Powers In Essentially Linear Time"
More information about the gmp-devel