What Jason is saying (I think) is that currently xgcd (not gcd) doesn't use Moller's patches as such. It will in future, but not at the moment. So whatever guarantees you had before, you still have now. But that will soon change.
The other issue here is that there are multiple algorithms here and it is quite likely that very small examples will use the basic xgcd which may well guarantee minimality. Only if you have say hundreds of thousands of bits will the algorithm used not return minimally guaranteed results. I'm sure when the time comes we can give some explicit million digit integers for which minimality is not guaranteed. Bill. On Jan 12, 5:23 am, mabshoff <michael.absh...@mathematik.uni- dortmund.de> wrote: > On Jan 11, 9:20 pm, "Jason Martin" <jason.worth.mar...@gmail.com> > wrote: > > Hi, > > > 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. > > Ok. > > > 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 is not the problem. The problem that in the docstring we give an > example where minimality is not guaranteed while svn1555 gives > minimality in this case. I tried a couple other xgcd examples and > could not find another sequence where this behavior was shown, so it > would be nice to find such a sequence. If you have any hints how to > construct such an example it would be nice if you told me :) > > > That way it wouldn't matter if the result was "minimal" or not. > > > Jason Worth Martin > > Asst. Professor of Mathematicshttp://www.math.jmu.edu/~martin > > 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 -~----------~----~----~----~------~----~------~--~---
