A perfect power, and then?

[Torbjorn Granlund]

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

  Ah, and if we're brain storming, yet another variant would be to compute
  an extra limb (or maybe only half a limb) of precision when we compute
  the 2-adic k'th root. If the extra limb is non-zero, then the input can't
  be a k'th power. That's going to asymptotically a bit slower than the
  O(1) logarithm trick, but it can have a much smaller false positive
  rate.
  
That's a good idea, and easy to implement correctly as well.  If I
understand the current code correctly, it goes to lengths at computing
not one extra bit.  Making it more limb-oriented is probably a good idea
irrespective of your suggestion.

I am now thinking of the usages and typical operands of these usages.

When asking "is N a perfect power?" I assume it will be common that N is
not actually a perfect power.  We should optimise for that.

When computing mpz_rootexact(R,N,k) for a specific k, the user claims
that she knows N^{1/k} is an integer.  We should optimise for that,
meaning that we should not compute a b-adic root for some small b first.

When computing some function mpz_is_this_a_kth_root(R,N,k) for a
specific k, then I would again assume N is not usually a kth root.

It is probably not uncommon that we want a root for perfect powers, as
Marco suggested.  Then it will be faster to compute it as a side effect
of checking its existence.  (I.e., mpz_perfect_power_p + mpz_rootexact
will be slower, but so will mpz_perfect_power_p_and_get_me_k +
mpz_rootexact...)

Any more scenarios?

Whatever interface we choose, we should make sure we can implicitly or
explicitly determine the likelihood for N being a perfect power.

For computing mpz_rootexact(R,N,k) the optimal strategy is most likely
to compute the upper half using Euclidean norm, and the lower part using
b-adic norm.  We don't have Euclidean code for nth root that is
O(M(log(N^{1/k}))) = O(M(log(N)/k)) on average for arbitrary N.  It
should be mucg easier to write such code for perfect k powers N than for
an arbitrary N.  Like with Jebelean's divexact trick, this should use a
few bits of "overlap" in order to glue the upper and lower halves
together.

(Why would this be faster?  The computations are both superlinear, 2 half
as large computations must then be (asymptotically) faster than one full
size computation.)

-- 
Torbjörn