A perfect power, and then?

[Torbjorn Granlund]

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

  > Sounds right.  Such convolution type sum-of-products might want a
  > separate function, returning 3 limbs.
  
  But I'm not talking about a convolution, but about the complete
  powering. If x is a candidate nth root, and x^n is of size s bits, I
  want to compute a decent approximation of floor (x^n / 2^{s -
  GMP_NUMB_BITS}) (a single limb value), and compare that to the input
  number which x is supposedly a root of. Simplest way would be to use the
  binary powering algorithm, and represent all intermediates as a
  normalized limb sized mantissa and a shift count. To use it, one needs a
  strict bound on the error, which I guess would depend on n, but I don't
  think the error analysis is very difficult. One might even consider
  using the floating point hardware.
  
I misthought...  I was someplace in a mid-product limb land, where a
convolution-type thing would be the centre of a binary powering
algorithm.

I would like to avoid fp hardware in the portable parts of GMP.  Looping
around umul_ppmm, keeping the msb = 1 should give a few correct bits.

The error will depend on the limb size and on n.  For the ASL patch
(artificially small limbs) we might not be able to make this work.

  I think that's going to be a lot faster than computing any middle limbs,
  and that it's going to rule out almost all numbers which aren't
  perfect n-powers.
  
It seem very reasonably.

I need to look into the present algorithn to get completely convinced,
though.  I was under the impression that it in practice rejected bad n
values after a b-adic run at few-word "precision".

-- 
Torbjörn