division-free binary-to-decimal conversion

Torbjorn Granlund tg at gmplib.org
Mon Oct 7 10:45:56 CEST 2013

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?

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.

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?

(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.)


More information about the gmp-devel mailing list