The solution is simply to add a function mpn_gcdext_min which
guarantees a "minimal" solution which is invariant across platforms.
It's more than a few percent to guarantee this in general, but the
Sage doctesting framework isn't particularly tolerant of changes in
output of functions.
Of course
On Tuesday 13 January 2009 19:26:07 Carl Witty wrote:
> On Jan 13, 2:38 am, ja...@njkfrudils.plus.com wrote:
> > > > 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 mini
On Jan 13, 2:38 am, ja...@njkfrudils.plus.com wrote:
> > > 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 bi
On Tuesday 13 January 2009 02:23:44 mabshoff wrote:
> On Jan 12, 2:36 pm, Bill Hart wrote:
>
> Hi,
>
> > 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, y
I checked through the code quickly and indeed mpz_gcdext calls
mpn_gcdext which simply implements the Lehmer algorithm (and some
optimisations for one and to limb divisions).
I'll do some work on the gcd and xgcd code for the next release. At
the present time I'm working on something different.
On Jan 12, 2:36 pm, Bill Hart wrote:
Hi,
> 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.
Ok, thanks fo
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
On Jan 11, 9:20 pm, "Jason Martin"
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 cou
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.
C
