Recent changes to mpn_get_str/mpn_set_str

Niels Möller nisse at
Wed Feb 15 08:59:39 UTC 2017

tg at (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, 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 mailing list