division-free binary-to-decimal conversion

Torbjorn Granlund tg at gmplib.org
Mon Oct 7 11:32:27 CEST 2013

Zimmermann Paul <Paul.Zimmermann at inria.fr> writes:

  we mean "faster than GMP's conversion functions", but still using GMP for the
  low-level operations.
Then please say so in the paper.

  not only. For large operands we believe there is still room to improve our
  code. In particular an important part of the total time is spent in the
  initial long division: instead of dividing by 10^k we first divide by 2^k,
  then by 5^k. But this induces an unbalanced division (not 2n bits by n bits)
  and we noticed GMP was not optimal for this (some improvements have been made
  in the development version). In the "scaled remainder tree", we have to
  multiply by 10^k, which is currently not done by 2^k * 5^k in our code.
Keeping low zero limbs out of the powers of 10 was a significant win in
my code.


More information about the gmp-devel mailing list