Recent changes to mpn_get_str/mpn_set_str

[Torbjörn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  tg at gmplib.org (Torbjörn Granlund) writes:
  
  > It would be possible to improve the general speed for binary-to-string
  > conversion (i.e., mpn_get_str).  One idea is to pre-invert the larger
  > powers.  The highest power is used just once, so nothing to improve
  > there.  The 2nd highest power is used twice and is now thererby
  > implicitly inverted twice.  The 3rd highest power is used four times,
  > and is therefore implicitly inverted four times, etc.
  
  Maybe one can make some additional savings by computing all neeed
  inverses up front, together? Say the base is b, and that we have
  computed v as an n-limb approximation of b^{-k}, to be used in the
  middle of the divide-and-conquer conversion.
  
  Then sqrhi(v) should be a decent n-limb approximation of b^{-2k}, and a
  single Newton step should give us close to 2n accurate limbs of b^{-2k}.
  So if we need the latter value, we can get it without starting from
  scratch.
  
  Now, probably not a big gain, since the final Newton step is the most
  expensive, and sqrhi isn't free, but I guess it could bring some
  speedup.
  
I've never analysed how much gain that would give.

The power series does not consist of B, B^2, B^4, ..., but rather B^k
such that (B^k)^2 >= a (a being the number to convert) for minimal k,
and than (B^ceil(k/2)), B^(ceil(k/4)), ...

Using a previous inverse as a starting approximation for the next larger
power will still work, but one will need to multiply by B.  Keeping
track of errors might be non-trivial.

Currently, I am more interested in speeding up the basecase code since
that is the code which is most commonly used.  Given the nature of the
subquadratic code, the basecase code's performance matters for operands
up to tens of thousands of digits.

-- 
Torbjörn
Please encrypt, key id 0xC8601622