Small operands gcd improvements

Niels Möller nisse at
Tue Jul 30 20:31:58 UTC 2019

tg at (Torbjörn Granlund) writes:

> The gcd_2 function of mpn/generic/gcd.c uses a loop with an randomly
> taken branch, and therefore is slow.

I think I at some point attempted a version with masking tricks, similar
to the C gcd_1, but I didn't manage to get any useful speedup.

> What can we do?
> 1. Define mpn_gcd_11.

What should its input requirements be? Should it require one argument,
either argument, or both argument to be odd? If even inputs are allowed,
do we also allow zero input?

To me it makes some sense to require that common factors of two are
taken care of at top-level, and at least rule out the case of two even
inputs to gcd_11.

> 2. Add a new entry point mpn_gcd_11 to existing assembly mpn_gcd_1.

I hope we don't we have to do that all at once, but can the mpn_gcd_11
entry point be optional (via HAVE_NATIVE_*)?


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