ni...@lysator.liu.se (Niels Möller) writes: Torbjorn Granlund <t...@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 _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel