Recent changes to mpn_get_str/mpn_set_str
nisse at lysator.liu.se
Wed Feb 15 08:59:39 UTC 2017
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.
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel