Recent changes to mpn_get_str/mpn_set_str
Torbjörn Granlund
tg at gmplib.org
Wed Feb 15 13:06:05 UTC 2017
nisse at lysator.liu.se (Niels Möller) writes:
Is the time totally dominated by the squarings?
As exponents grow, sure.
Or would it make sense to use sliding-window powering, with table size
chosen so that all tabulated powers are single-limb?
I am not sure sliding-window powering makes much sense for powering in Z
(as opposed to in a ring).
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.
I am not familiar with that algorithm, but I see very little room for
improvements of b^e in Z when e is large. My reasoning as that we want
to compute a number of n bits, and squaring is the fastest way of
reaching that. In particular, no clever combination of multiplications
will be faster.
In mpz/n_pow_ui.c we do what we can for small b and e, e.g., perform
some operations on plain mp_limb_t variables. For radix conversion, we
arrange things so that the bases are never small, so the plain mpn_pow_1
should be very hard to beat.
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-devel
mailing list