Hi Nils,
I've been looking at
http://www.sagetrac.org/sage_trac/ticket/1482
and approximately diagnosed the problem (see comments on the ticket),
but it's not clear to me exactly how to proceed.
The new underlying gcd code produces quite inscrutable output, for
example:
sage: xgcd(3, 3)
(3, 0, 1)
sage: xgcd(3, 6)
(3, -3, 2)
sage: xgcd(3, 9)
(3, -8, 3)
sage: xgcd(3, 12)
(3, -3, 1)
sage: xgcd(3, 15)
(3, -14, 3)
sage: xgcd(3, 18)
(3, -17, 3)
sage: xgcd(3, 21)
(3, -20, 3)
sage: xgcd(3, 24)
(3, -15, 2)
sage: xgcd(3, 27)
(3, -26, 3)
sage: xgcd(3, 30)
(3, -29, 3)
sage: xgcd(3, 33)
(3, -32, 3)
sage: xgcd(3, 36)
(3, -35, 3)
sage: xgcd(3, 39)
(3, -38, 3)
sage: xgcd(3, 42)
(3, -41, 3)
sage: xgcd(3, 45)
(3, -44, 3)
sage: xgcd(3, 48)
(3, -15, 1)
sage: xgcd(3, 51)
(3, -50, 3)
It's very hard to see any rhyme or reason in that. Certainly the GMP
documentation doesn't guarantee any properties of the cofactors,
apart from bezout, either at the mpz or mpn levels, so it's not a bug.
I'm inclined to do the following in Sage. Provide a "fast" flag which
just calls GMP and doesn't provide any guarantees about the output
(apart from satisfying bezout). If "fast" is False (default), then we
convert to a "standard" form, which should be unique, mathematically
sensible, and carefully documented.
But having thought about it for a while, it's not even clear to me
what exactly the right definition of "standard" should be. I don't
quite understand the minimality condition you proposed.
Apart from the kind of special case listed above, GMP does seem to
follow some "rules", but I'm not sure they are always satisfied, and
we can't rely on them since the GMP documentation doesn't promise
anything.
For example, if 0 < a < b, then xgcd(a, b)[1] always seems to be
negative and xgcd(a, b)[2] always positive, but it swaps around if 0
< b < a:
sage: xgcd(11, 17)
(1, -3, 2)
sage: xgcd(17, 11)
(1, 2, -3)
i.e. it looks like it swaps them to make a < b, and then swaps the
cofactors at the end.
It generally seems to handle input signs in the same way, i.e. it
first does xgcd(|a|, |b|), then throws the signs back in at the end:
sage: xgcd(11, 17)
(1, -3, 2)
sage: xgcd(-11, 17)
(1, 3, 2)
sage: xgcd(11, -17)
(1, -3, -2)
sage: xgcd(-11, -17)
(1, 3, -2)
But none of this is particularly canonical.
What's the "right" way to do this?
david
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
