Cofactor canonicalisation of mpn_gcdext

Niels Möller nisse at
Thu Dec 3 16:56:57 CET 2009

Torbjorn Granlund <tg at> writes:

> nisse at (Niels Möller) writes:
>   Below an updated patch (also in my repository at shell), which seems to
>   give the correct results and canonical cofactors. There's most likely a
>   performance regression, due to the naive Euclid algorithm used in
>   gcdext_1.
> We can worry about later, either before GMP 4.4 get out of the door or
> for GMP 4.5.

I gave div1 a try, and it actually seemed to make gcdext slower (./speed
-c -s1 mpn_gcdext on my x86_32 laptop).

> If you think this code is right, don't be shy: please push it into the
> main repo and check tomorrow.

Pushed in now.

Benchmarking on shell, I get (for the old gcdext code):

$ ./speed -c -s1-5 mpn_gcdext
overhead 6.06 cycles, precision 10000 units of 4.66e-11 secs, CPU freq 21438.42 MHz
1             2337.48
2             4782.41
3             7249.04
4             9705.38
5            12155.41

and for the just pushed in code, with one /-division per iteration in gcdext_1, I

1             1585.38
2             4659.20
3             7091.04
4             9503.12
5            11924.64


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list