division-free binary-to-decimal conversion

[Zimmermann Paul]

       Torbjörn,

> From: Torbjorn Granlund <tg at gmplib.org>
> Date: Mon, 07 Oct 2013 10:45:56 +0200
> 
> I did a quick first read.
> 
> I take it that "faster than GMP" means "faster than GMP's conversion
> functions, using GMP"...  Or did you actually beat GMP without GMP?

we mean "faster than GMP's conversion functions", but still using GMP for the
low-level operations.

> I cannot recall how the present mpf conversion code works, since I don't
> actively develop that.
> 
> For integer conversion, the most important problem with the present code
> is small operands performance, if I read correctly.

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.

> For larger operands, there is an optimisation which applies to the
> current code which might also apply to the proposed new algorithm.  The
> idea is to compute a highest power b^k of the target base b such that it
> is around X^(1/3) instead of X^(1/2), where X is to be converted.  The
> high power is then applied twice.  This should be an optimisation in
> itself, but much more so if one saves 1/b^k for th 'mu' division call.
> I strongly suspect that that optimisation would cover the current 20%
> edge of your code.  But surely you could do something similar?

not sure, we have to think about that.

> (In Figure 1, it seems that your GET_STR_PRECOMPUTE_THRESHOLD is
> slightly too large for your system.  Also, one might interpret this as a
> diagram for quadratic algorithms, but only part of the range will
> actually use that.)

yes indeed.

Paul