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 --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
