A perfect power, and then?

[Niels Möller]

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?

> Any suggestions for a new function interface?

I think

     mp_bitcnt_t mpz_perfect_power_p (mpz_t x);

is mostly right. If x is a perfect power, return an exponent > 1, otherwise
zero. Some questions:

1. Should it be required to return the *largest* exponent?

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

3. Do all reasonable algorithms compute the root? If so, it would make a
   lot of sense to have an (optional) argument where the root can be
   returned. E.g.,

     mp_bitcnt_t mpz_perfect_root (mpz_t root, const mpz_t x);

   (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
   well).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.