Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> nisse at lysator.liu.se (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 http://gmplib.org/devel/testmachines.shtml 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
           mpn_gcdext
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
get

1             1585.38
2             4659.20
3             7091.04
4             9503.12
5            11924.64

Regards,
/Niels

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