Joel, I agree with your summary. Here is a graph I plotted timing Pari (red) vs NTL (blue) for factoring in ZZ, where there are at least two polynomial factors.
http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/factor.png The scale is log to the base 2. At about length 256 polynomials Pari ran out of memory and the factorisation stopped. As far as I know both NTL and Pari that I used are linked against and are using GMP with all the appropriate patches. Clearly NTL is asymptotically fast for polynomials of large length, but Pari is faster for shorter polynomials. I didn't really take the bit size past 2000 or so. Bill. On 20 Dec, 00:38, Bill Hart <[EMAIL PROTECTED]> wrote: > 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/ -~----------~----~----~----~------~----~------~--~---
