No, we can't guarantee minimality. The xgcd that you're seeing right now in MPIR only uses Moller's code when it calls to gcd. It isn't as nice as the xgcd that is in GMP 4.3. Hopefully, we will be able to re-invent that wheel since I couldn't find a LGPL v. 2+ version of Moller's xgcd code.
Can the Sage doctest code just perform the integer linear combination to check correctness without having to test against a known value for the coefficients? Meaning if we have g, s, t = xgcd(a,b) can the doctest just verify that g == a*s + b*t and that g is the known value for the gcd? That way it wouldn't matter if the result was "minimal" or not. Jason Worth Martin Asst. Professor of Mathematics http://www.math.jmu.edu/~martin On Sun, Jan 11, 2009 at 11:57 PM, mabshoff <michael.absh...@mathematik.uni-dortmund.de> wrote: > > Hi, > > I just build a svn1555 eMPIRe.spkg and the good news is that it seems > that it can be "just dropped" a current install, i.e. we don't have to > bump each spkg depending on gmp for the upgrade. So far I am only > testing x86-64 Linux, but OSX is next. That makes the switch > significantly less disruptive. > > While looking at doctest failures I found the following in /devel/ > sage/sage/rings/integer.pyx", line 3547: > > gmp + Nils Moeller patches: > [old docstring] > Without minimality guarantees, weird things can happen: > > sage: Integer(3)._xgcd(21) > (3, -20, 3) > sage: Integer(3)._xgcd(24) > (3, -15, 2) > sage: Integer(3)._xgcd(48) > (3, -15, 1) > [end old docstring] > > The version of Nils Moeller's patches in eMPIRe seems to always return > the minimal solution. Is that guaranteed by the new code? I ran a > couple dozen examples and didn't find any case where we didn't get the > minimal solution, but I would be happy if someone could tell me that > this is guaranteed. In that case we don't need to minimal parameter in > Sage for the xgcd any more. > > Cheers, > > Michael > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
