Recent changes to mpn_get_str/mpn_set_str

Torbjörn Granlund tg at
Thu Feb 2 16:02:39 UTC 2017

"Marco Bodrato" <bodrato at> 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.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list