I get about 7us per loop on sage.math for Pari for the exponentiation. So perhaps this is all architecture dependent. This would not surprise me in the slightest.
At any rate, I suspect the algorithms used for factorisation are implemented quite differently between NTL and Pari. Since both Pari and NTL use GMP mpn's for underlying integer arithmetic in SAGE, I think the algorithms being used for factorisation are much more relevant than the speed of basic arithmetic, which should be the same for both. The other point is that both Pari and NTL use finite field stuff to factor polynomials over the integers. So the speed of integer arithmetic is almost irrelevant. Having said all that, it is surprising that NTL is behind Pari for polynomial factorisation, given the amount of work Victor put into this. Can you try your example problems on sage.math? Bill. On 19 Dec, 18:40, "Joel B. Mohler" <[EMAIL PROTECTED]> wrote: > 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/ -~----------~----~----~----~------~----~------~--~---
