I get 6us per loop for the exponentiation in NTL on sage.math.
On 20 Dec, 00:19, Bill Hart <[EMAIL PROTECTED]> wrote:
> 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/
-~----------~----~----~----~------~----~------~--~---
