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