I should also add that our hacked together version was derived from Niels' original implementation anyway. The main thing I had done was make it work for xgcd and not just gcd (as GMP had already done with their version) and later adjust the normalisation so that it could be used by Pari. I did also spend a fair bit of time working out how to make it work with the basecase GCD code we had.
The xgcd thing was actually a lot of work because it was not obvious to me at the time how to efficiently turn a half gcd into an xgcd. It's obvious to me now, but at the time I spent many days working on this. Anyhow, I am pleased we now have not just a working asymptotically fast version, but a neat, practically efficient version of this in MPIR. Bill. On 5 January 2012 08:39, Bill Hart <goodwillh...@googlemail.com> wrote: > Jason, those speedups look great. Always good to see things getting faster! > > Regarding the GCD code I want to mention that this is the version that > has been in GMP for some time. Their code was neater than ours and > performed slightly better, so I recommended we use their version > instead of the version I had hacked together. > > The credit for this code is almost certainly due to Niels Moller and > Torbjorn Granlund. The algorithm itself is due to Niels. If someone > else also worked on this, please let us know and we can credit them > for it. Niels' paper is here: > http://www.lysator.liu.se/~nisse/archive/S0025-5718-07-02017-0.pdf > > Of course that is the same algorithm as the one we had implemented, > just a much improved implementation of it. > > Bill. > > On 5 January 2012 07:35, Jason <ja...@njkfrudils.plus.com> wrote: >> Hi >> >> MPIR 2.5.0 was released on 5th January 2012. >> >> * source tarballs: http://www.mpir.org/mpir-2.5.0.tar.bz2 >> http://www.mpir.org/mpir-2.5.0.tar.lzma >> * documentation: http://www.mpir.org/mpir-2.5.0.pdf >> >> See the MPIR website (www.mpir.org) for known issues and a list of supported >> platforms/hardware in the form of the test matrix. >> >> The main features and changes for this release are: >> >> Bug Fixes: >> >> * Correct rounding mode make check tests >> >> Speedups: >> >> * x86_64 fat build now uses RIP relative addressing >> * Toom22 speedup via assembler >> * New x86_64 assembler code >> * New Toom eval function using the new assembler code >> * Detect another Sandybridge CPU >> * New GCD code (by the GMP project) >> >> Features: >> >> * General cleanup of old features >> * Upgrade intenal component YASM >> * MSVC build tweeks >> * New experimental MSVC python build system >> >> Changes: >> >> * Remove explicit support for thumb m68k and sh cpu's >> >> >> Regards >> The MPIR Team >> >> -- >> 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. >> -- 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.
