A perfect power, and then?

Torbjorn Granlund tg at gmplib.org
Thu Oct 25 14:16:02 CEST 2012

nisse at lysator.liu.se (Niels Möller) writes:

  bodrato at mail.dm.unipi.it writes:
  > I propose
  >  mp_bitcnt_t mpz_perfect_root (mpz_t root, const mpz_t x, mp_bitcnt_t nth);
  > If nth != 0, check if x is a perfect nth-root (generalize perfect_square).
  > If nth == 0, search for a non-trivial relation root^e = x, and return e.
  Both variants make sense, but I'm not sure they should be the same
Do you have a proposal for two separate functions?

I, too, like separate functions.  But then inventing good names is one
of these hard CS problems.  :-)

We already have mpz_divexact*.  It might make sense to have call (one
of) the new function(s) mpz_rootexact.

  I think it's desirable that mpz_perfect_power_p can be re-implemented by
  a call to new new function followed by a very simple check on the return
  value. Then we need distinct return values for the case |x| <= 1 (which
  are considered perfect powers) and non-powers. Using 1 for the former
  and 0 for the latter seems like a reasonable choice to me.
mpz_perfect_power_p is one line currently, if we reimplement it, then I
demand that the new implementation is shorter.  :-)

We should split mpn/generic/perfpow.c into a few files.  I think I'll
make a bsqrt.c and broot.c as a start.  Perhaps broot.c should use Niels'
function instead, I cannot recall the differences, if any.


More information about the gmp-devel mailing list