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.
--
Torbjörn
More information about the gmp-devel
mailing list