Cofactor canonicalisation of mpn_gcdext
nisse at lysator.liu.se
Thu Dec 3 16:56:57 CET 2009
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
> 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
and for the just pushed in code, with one /-division per iteration in gcdext_1, I
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel