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. Bill. On Jan 13, 2:23 am, mabshoff <michael.absh...@mathematik.uni- dortmund.de> wrote: > On Jan 12, 2:36 pm, Bill Hart <goodwillh...@googlemail.com> 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 for clearing this up. To me those finer details are know > since I don't root around in the internals of gmp/mpir. > > > 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. > > Thanks, we might want to add that to the docstring and remove the > explicit example. > > > Bill. > > 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 -~----------~----~----~----~------~----~------~--~---
