Recent changes to mpn_get_str/mpn_set_str
Torbjörn Granlund
tg at gmplib.org
Thu Feb 2 16:02:39 UTC 2017
"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:
Maybe I'll try, the basecase...
I take this as a promise. :-)
If coming from the sub-quadratic code, there will be a suitable
precomputed power of 'big_base' (which is b^k < B, k maximal; b is the
conversion base and B the limb base). Any number to be converted should
be just < than this power.
If coming directly from the external caller (e.g. mpz_get_str) no such
power will be available. One should be computed with mpn_pow_1 (or a
new mpn_1_pow_1 (or whatever to call it; it would take a mp_limb_t base
unlike mpn_pow_1 which takes a (mp_ptr,mp_size_t) base).
(Incidentally, mpz/n_pow_ui.c contains its own well-tuned powering
code. This code ought to be moved to mpn in some form. That's a
separate project, of course.)
Possible improvements:
When coming from the sub-quadratic code, there will be some degree of
invariance for the division by the same big_base power. This suggests
that we should pre-compute at least the inverse of the leading limb
(i.e., invert_limb) or perhaps a full inverse. It would save not too
far from 50% of the work if we then also had mpn_mulhi.
Since GET_STR_DC_THRESHOLD has a median of just 13, it would make some
sense to compile-time compute and table powers up to
GET_STR_DC_THRESHOLD for base 10. For CPUs with mpn_mulhi (currently
none) tabling also the inverses (or just the inverses!) also makes sense.
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-devel
mailing list