On Wed, Dec 19, 2007 at 06:03:32PM +0000, John Cremona wrote: > I'm surprised by your comment about integer arithmetic, since both > pari and NTL use gmp. AT least, they both *can* use gmp though it > might not be the default. Do you know of the pari and NTL you are > using are gmp-based?
Well, I know I'm using the default 2.9 build, and I know I see these timings: sage: p=pari(1234157) sage: r=ntl.ZZ(1234157) sage: timeit p^300 10000 loops, best of 3: 33.8 �s per loop sage: timeit r^300 10000 loops, best of 3: 21.7 �s per loop I realize the exponentiation is a fairly narrow minded view of the whole of integer arithmetic, but the difference there seems a little striking to both be using gmp. However, I guess it really isn't fair since the pari is a gen object, but a the NTL ZZ is known as an integer. So, here this might be more fair to compare an ntl.ZZX with pari: sage: s=ntl.ZZX([1234157]) sage: timeit s^300 10000 loops, best of 3: 94.6 �s per loop I don't know, that seems bizarre to me! -- Joel > > John > > On 19/12/2007, Joel B. Mohler <[EMAIL PROTECTED]> wrote: > > > > 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 > > > > > > > > > > -- > 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/ -~----------~----~----~----~------~----~------~--~---
