A perfect power, and then?

[Torbjorn Granlund]

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

A disadvantage is that this is an incompatible change.

  Some questions:
  
  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
smallest.

  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 number.
  
     (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).
  
We use Bernstein's "Detecting Perfect Powers In Essentially Linear Time"
in mpn/generic/perfpow.c.

-- 
Torbjörn