Significant speedup divrem of very short numbers
Niels Möller
nisse at lysator.liu.se
Fri Nov 15 19:23:33 UTC 2019
Andy <borucki.andrzej at gmail.com> writes:
> Although GMP is designed for very long numbers, sometimes systems using it
> would have task divide amd mod very short numbers : one limb by one
> limb.
If you use the mpn-level functions of gmp, and have divisors that are
always or usually single limb numbers, you'll get less overhead if you
call mpn_divrem_1 rather than mpn_tdiv_qr.
> For example if we factor this number.
For factoring single limb numbers, the factor program from GNU coreutils
is likely much faster than anything using mpn_tdiv_qr. It uses trial
division with precomputed p-adic inverses of primes up to some limit,
followed by Pollard-Brent rho using Montgomery redc rather than plain
division.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list