Recent changes to mpn_get_str/mpn_set_str

Torbjörn Granlund tg at
Wed Feb 15 13:06:05 UTC 2017

nisse at (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, 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.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list