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/
-~----------~----~----~----~------~----~------~--~---
