Recent changes to mpn_get_str/mpn_set_str

[Torbjörn Granlund]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

  Il Gio, 26 Gennaio 2017 1:31 pm, Torbjörn Granlund ha scritto:
  > 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.
  
  We may also try the division-free algorithm explored by Bouvier-Zimmermann
  in their paper: https://members.loria.fr/PZimmermann/papers/get_str.pdf
  
I took a quick look at that now.

For the basecase code, if I understand correctly, they start by dividing
by a suitable power of the conversion base (3. Division-free conversion,
2nd line) then multiply repeatedly by the base.

We do that in our current code, but at a limb level.  I suppose dividing
by a larger power as they do is much better as general schoolbook
division is much more efficient than mpn_divrem_1.

But I wouldn't call their algorithm "division free"...

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