A perfect power, and then?
Niels Möller
nisse at lysator.liu.se
Wed Oct 24 09:20:49 CEST 2012
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.
More information about the gmp-devel
mailing list