Recent changes to mpn_get_str/mpn_set_str

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> We have some pow_1 code of different leves of complexity; mpz/n_pow_ui.c
> is pretty hairy while mpn/generic/pow_1.c is simpler.  I think the
> latter is perfectly suitable for get_str's needs (the mpz code checks
> for bases which are much smaller than the max limb value, then
> conditionally performs some limb steps).

Is the time totally dominated by the squarings?

Or would it make sense to use sliding-window powering, with table size
chosen so that all tabulated powers are single-limb?

To speed up exponentiation for one or a few fixed bases (which seems
relevant for base conversion), one can use Pippenger's algorithm,
https://cr.yp.to/papers.html#pippenger. What's nice is that it cuts down
on the number of squarings. But perhaps it doesn't help so much in the
case of pow_1 (non-modular exponentiation), where elements are of very
different size as higher powers are computed.

Regards,
/Niels

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