Recent changes to mpn_get_str/mpn_set_str

[Torbjörn Granlund]

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