A perfect power, and then?

[Torbjorn Granlund]

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

  I guess this means: Avoid using functions from libm, and avoid using
  floating point in critical loops. Right? There's a (non-critical)
  floating point operation in mpn_perfect_power_p involving some logarithm
  table.
  
Right.  I would actually avoid the latter too, but I am aware of that we
have a small number of such things.

  > 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.
  
  It would make some sense to introduce an mpn_powhi, which computes an
  approximation of the high n (normalized?) limbs. Would be useful also
  for mpfr, I guess. It would either have a documented maximum error, or
  it could return an error bound (I imagine the error bound could be
  slithly different for plain binary exponentiation and window based
  exponentiation).
  
It seems better to have an error bound than a surprise error that might
be to large and require recomputation.

  > 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".
  
  If I understand this correctly, most bad n ought to be rejected as soon
  as the precision is xn+1 or larger.
  
I just got a crazy idea.  Compute the logarithm of the number (to a few
bits of precision, perhaps using table lookup).  Multiply this logarithm
by k.  Exponentiate using the logbase (again using a small table).
Conservatively compare to number being investigated.

-- 
Torbjörn