Recent changes to mpn_get_str/mpn_set_str

Marco Bodrato bodrato at
Thu Feb 16 21:02:09 UTC 2017


Il Mer, 15 Febbraio 2017 7:19 pm, Niels Möller ha scritto:

> But on the other hand, it might be better to note that, e.g., 10^19 fits
> in 64 bits, and compute 10^e as (10^19)^(floor(e/19)) * 10^(e mod 19).
> Or even better, handle the power of 2 separately and note that 5^27 fits
> in a 64-bit limb.

This is basically what the code I sent a few days ago does. I mean:
 - remove every 2 factor from the base before exponentiation;
 - exploit the pre-tabled big_base = base^chars_per_limb;
 - compute base^(exp mod chars_per_limb) within a limb (powlimb);
 - compute big_base^(floor(exp/chars_per_limb)) with mpn_pow_1;
 - a final mul_1 to combine the last two steps.

After this, the result is shifted to obtain a normalised divisor. Needed?
Not needed? maybe the shift can be avoided with a cleverer exponentiation?

Not surprisingly, the best speed-up is obtained with base 192=3*64.

Best regards,


More information about the gmp-devel mailing list