Ticket
http://trac.sagemath.org/sage_trac/ticket/1558
has some new code to use NTL to factor members of ZZ[x]. I'm doing some
benchmarking to confirm or deny the comments in polynomial_element.pyx factor
method. Here's a very brief summary of what I'm finding. I may or may not
provide more detail later to substantiate these claims. For the most part they
are not difficult to substantiate.
Here's my findings:
1) pari is faster with polynomial of degree 30-300. For higher degree, NTL
wins
and wins big asymptotically -- degree 2000 random poly takes "forever" with
pari
and 45 seconds with NTL.
2) pari seems to be a bit better when coefficients are larger but degree is
still low. For example, NTL is very fast for small degree (<10), but once we
start choosing larger coefficients (140 bits), pari becomes much more
competitive. However, this point seems fraught with special cases. I think
the
point may be that pari integer arithmetic beats NTL integer arithmetic, but
naive testing with ntl.ZZ and pari('') are indicating otherwise.
3) My tests seem to indicate that NTL's performs better when there are small
factors, but it doesn't seem a decisive difference. This doesn't seem real
helpful for choosing an algorithm in general though. It could be a point to
keep in mind for more specialized uses of factoring when you might know more
about the poly in hand.
I'd be curious if there are any comments about this. I'm going to change the
criteria in ticket 1558 to make pari factor when degree is between 30 and 300
and otherwise let NTL factor.
--
Joel
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
