Thanks for the references -- it is very good that the gmp code is so well documented with references to the literature.
It never ceases to amaze me how much improvement is possible on Euclid! John On 9/12/07, David Harvey <[EMAIL PROTECTED]> wrote: > > > On Sep 12, 2007, at 5:48 PM, John Cremona wrote: > > > Where are the algorithms behind these impressive speed-ups documented > > -- or is it done by clever implementation? Either way they should be > > published for posterity, or at least documented ! > > The code was taken from the first section of > > http://gmplib.org/devel/ > > I don't know the exact algorithm used, but it probably has complexity > O(M(n) log n), where M(n) is the time required to multiply two n-bit > numbers. Using asymptotically fast integer multiplication, that's O(n > log^2(n)) (plus some log log factors). There's a whole family of gcd > algorithms with that complexity, see for example > > http://perso.ens-lyon.fr/damien.stehle/BINARY.html > > The old code (i.e. in GMP 4.2.1 and 4.2.2) has complexity O(n^2). > > david > > > > > -- John Cremona --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
