Significant speedup divrem of very short numbers

[Niels Möller]

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.