Cofactor canonicalisation of mpn_gcdext
tg at gmplib.org
Thu Dec 3 14:48:10 CET 2009
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.
There was one subtle problem left by the previous patch. After reducing
numbers for a while, the gcdext code may find that the current two
values are equal, and hence it has found the gcd and should return. But
with which cofactor? Which of the two current cofactors is the canonical
one depends on the reduction leading up to equality, which we don't keep
track of. So in this case, we have to compare the two cofactors and
return the smallest one.
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.
Bill and John, it would be very useful if you (since you caused all this
trouble...!) could test the code and check if it works as you wish.
Please confirm that it works in general, and also in for the discussed
Niels, how tight is the test code now? If we agreed on leaving no
ambiguities (such as for gcd(u,u)) it would be useful if the testing
code would be as strict--that will help us when later optimising this
We need to improve the doc/gmp.texi text. (I could do that if I am told
the exact canonicalisation rules for the singularities.)
More information about the gmp-devel