Recent changes to mpn_get_str/mpn_set_str

[Niels Möller]

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.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.