Taking a look at the actual data from the timings I did, the time taken to factor varies much more in Magma than in NTL. Here are the Magma timings for length 341 polynomials:
341 1 1.020e+06 1.723e+06 341 2 9.600e+05 3.090e+06 341 3 1.937e+06 3.177e+06 341 4 8.900e+05 2.973e+06 341 5 2.200e+06 3.203e+06 341 6 1.120e+06 2.352e+06 341 7 9.200e+05 3.170e+06 341 8 1.075e+06 2.507e+06 341 10 1.167e+06 3.463e+06 341 12 1.383e+06 2.433e+06 341 15 2.177e+06 3.175e+06 341 18 1.173e+06 2.480e+06 341 22 9.500e+05 2.583e+06 341 26 1.233e+06 3.257e+06 Here are the times for NTL: 341 1 3.444e+06 3.740e+06 341 2 3.124e+06 3.634e+06 341 3 3.122e+06 3.707e+06 341 4 3.397e+06 4.052e+06 341 5 3.563e+06 3.797e+06 341 6 3.348e+06 4.000e+06 341 7 3.130e+06 3.895e+06 341 8 3.367e+06 3.684e+06 341 10 3.611e+06 4.001e+06 341 12 3.232e+06 3.776e+06 341 15 3.536e+06 3.978e+06 341 18 3.192e+06 3.744e+06 341 22 3.409e+06 3.833e+06 341 26 3.418e+06 3.787e+06 As you can see, the NTL timings differ between the best and worst times by about 10-15%, however the Magma timings differ from each other by a factor of up to 2 or 3. I believe this is because of small factors being removed at various stages due to some heuristics developed by Allan Steel as mentioned in the Magma documentation. If you look at the maximum times taken in each case, NTL is not that far behind NTL. Bill. On 20 Dec, 21:26, Bill Hart <[EMAIL PROTECTED]> wrote: > I fixed the four magma graphs above so that they take into account the > time to compute and divide by the content, since Pari and NTL > certainly do that. > > The result is just about the same. Magma is significantly faster for > longer polynomials, usually a factor of about 2.5, though it varies a > bit. > > Bill. > > On 20 Dec, 20:28, Bill Hart <[EMAIL PROTECTED]> wrote: > > > And here we go for generic polynomials: > > > Magma vs Pari: > > >http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/magp... > > > Magma vs NTL: > > >http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/magN... > > > Bill. > > > On 20 Dec, 20:13, Bill Hart <[EMAIL PROTECTED]> wrote: > > > > For comparison, here is our favourite non-free closed source package > > > vs Pari and NTL for factoring with two large factors: > > > > Magma vs Pari: > > > >http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/magp... > > > > Magma vs NTL: > > > >http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/magN... > > > > Something that may not be fair here is that Magma factors the content, > > > so I have divided the polynomials used by their content before > > > factoring them. But I didn't include the time taken to divide by the > > > content in the timing. Given that computing the content should be > > > almost instant generically, I don't see this as much of a problem > > > though. > > > > Bill. > > > > On 20 Dec, 18:46, Bill Hart <[EMAIL PROTECTED]> wrote: > > > > > I've redone both graphs since the generic NTL profiling code in FLINT > > > > was assuming that a length n polynomial had n+1 coefficients (my > > > > student had done this due to some confusion about the way coefficients > > > > were counted). > > > > > The graph for polynomials with two large factors (at least): > > > > >http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/fact... > > > > > and the graph for generic polynomials: > > > > >http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/fact... > > > > > Hopefully these are correct now. > > > > > Bill. > > > > > On 20 Dec, 17:49, Bill Hart <[EMAIL PROTECTED]> wrote: > > > > > > Here is the graph for generic polynomials: > > > > > >http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/fact... > > > > > > At about 1000 bits and length 6, NTL does seem to get ahead again. > > > > > > 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/ -~----------~----~----~----~------~----~------~--~---
