A perfect power, and then?

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I would like to avoid fp hardware in the portable parts of GMP.

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.

> 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).

> 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.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.