Replacing gcd_1 with gcd_11

Niels Möller nisse at
Sun Aug 18 18:54:58 UTC 2019

"Marco Bodrato" <bodrato at> writes:

> 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?

mpn_gcd_22 will be slower for that case. But I'm not sure if it that is

We will never reach the 2:1 case with user inputs, since mpn_gcd does an
initial division if u and v are of different limb size. And if we reach
it after one or more iterations of the hgcd/hgcd2 steps, or directly
after the initial division, then I think it's unlikely to have u and v
with bit sizes differing by many bits.


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