Indeed Nils Bruin was correct. When timing the computation of class
groups in Magma you need to set the bound for both the factor base
*and* the class group checking. In fact I had not noticed that Magma
has a function SetClassGroupBounds("PARI"); which tries to emulate
the level of rigour that Pari uses by setting both bounds
appropriately. This makes a substantial difference to the Magma times
especially for small discriminants.
Notes:
1) I do not compute the maximal order before computing the class group
(or at all in fact).
2) I do not attempt to change the representation of the field before
computing the class group.
3) I don't know how to separate the timings for computing up to the
factor base bound and for checking the class group in Pari so I can't
separate the times at this point. I don't believe this is advantaging
Pari anyway.
I also reckon that there are integer factorisation algorithms which
would complete arbitrarily fast if you started with the correct
parameters from the start. The thing is you don't know what they are
in advance, so I personally consider it cheating to have to figure out
good heuristics on behalf of an algorithm.
Of course if one is working with a single field repeatedly, many
functions may benefit from first computing the maximal order or from
changing the representation, so what I say is not quite fair. This is
admittedly easier to do in Magma. But Pari does not do 1 or 2, so in
the timings below I don't advantage Magma unfairly by doing so. Of
course in practice one should do as Nils recommends.
Anyway, here are the new times for quadratic fields (other degrees
will follow):
degree, bits, iterations: Pari Magma
2, 10, 10000 : 27s 57s
2, 20, 2000 : 25s 55s
2, 30, 300 : 25s 77s
2, 40, 100 : 50-80s ~267s
x^2 - 678650306441557*x + 232491039415161 : 5.81s 222s
x^2 + 400359911885097*x + 1023437292772615 : 8.33s 362s
x^2 + 788021445418312*x + 62108142321374 : 136s ....
x^2 + 310104001090081*x + 526420096868844 : 2.18s 126s
x^2 + 29148692184930*x + 697845351766239 : 1.45s 49.5s
Bill.
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
