Replacing gcd_1 with gcd_11

Marco Bodrato bodrato at
Sun Aug 18 11:06:11 UTC 2019


Il Dom, 18 Agosto 2019 9:44 am, Niels Möller ha scritto:
> Do we have all needed gcd_11 so we can switch to using it, without
> performance regressions?

As Torbjörn showed with some timings, replacing gcd_1 with gcd_11 can be a
performance regression when the size of the operands is really different
(gcd_1 uses a division before starting the loop). Was this healed?

> Attached patch updates the small-number cases at the end of mpn_gcd.
> This code would get simpler if we allowed one even input to gcd_11 and
> gcd_22.

The current code uses mpn_gcd_1 (up, 2, vp[1]) for the 2:1 case. That
function perform an initial modular reduction.

Is mpn_gcd_22 (up[1], up[0], 0, v1) as fast as that code?



More information about the gmp-devel mailing list