A perfect power, and then?

[Torbjorn Granlund]

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

  Nothing deep. It make sense that for small k (k'th root), it's a
  constant factor slower than binvert. And for large k, time should grow
  in the same way as powlo time grows with the bitsize of the exponent.
  
For a prospective mpn_rootexact, I assume the time will decrease with k,
given an n-bit input argument.  Right?

  > It does make some sense to have a bit count argument here instead of a
  > limb count argument.  The first few iterations will use limb precision,
  > but perhaps the caller needs such small precision that only 3 or 4
  > iterations are needed?
  
  For k'th root (k odd >= 3), I don't think bit count argument is very
  useful. One could consider a mpn_broot_limb (limb-sized input and output)
  with a bit size argument. We have nothing analogous for binvert_limb,
  though.
  
if we consider the problem of identifying perfect powers, I'd expect
arguments of say, 30 bits to become faster if we can avoid a few initial
iterations in some broot function.

Do you disagree?

  bsqrt is different, there we need a bit count to keep track of precision
  in the loop, so it makes sense to also use a bit count input. And then
  we have the peculiarity that if the input is of size b bits, the output
  is b-1 (since the top bit doesn't affect the square).
  
I am afraid I don't appreciate the difference.

I pushed a few new function, somewhat immature in implementation and
interface.  They are based on old mpn/generic/perfpow.c functions, but
with new names and slightly different parameters.  They also don't mask
off results (neither in the loops, nor at the end); this will allow for
a non-bit size argument of future versions.

-- 
Torbjörn