A perfect power, and then?

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

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

Agree this makes some sense. 1 would then be returned *only* for these
exceptional cases.

> The current perfpow.c algorithm doesn't, at least not when is can factor
> the number.

I see. What do you think of the interface

     mp_bitcnt_t mpz_perfect_root (mpz_t root, const mpz_t x);

then? We can allow root == NULL, for callers who don't care about the
root. And what's a good name?

Return value can then be defined as:

  1:      for input -1, 0 and 1. Also sets root = x.
  
  e >= 2: for other inputs which are perfect powers. e is then a
	  non-trivial divisor of the gcd of all exponents in the prime
	  factorization of x. Precisely which e is returned is left
	  unspecified. Also sets root to the unique e'th root with same
	  sign as x.

  0:      for all other inputs. (Should we allow root to be clobbered in this
          case?)

(We should also expose bsqrt, broot, sqrt_exact and root_exact, I guess.
I posted some new bsqrt and broot code to this list a few months ago).

And perfect_power_p could then be implemented efficiently as
mpz_perfect_root (NULL, x) > 0.

Regards,
/Niels

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