Here is a graph that uses slightly bigger coefficients, up to 10000 bits. http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/factor2.png
I don't see the speed increase you mentioned for large coefficients, but this might be due to some special properties of the polynomials you are factoring, or perhaps due to the particular architecture you have. Prime field arithmetic is probably quite architecture dependent, so that may contribute, I'm not sure. Bill. On 20 Dec, 02:47, Bill Hart <[EMAIL PROTECTED]> wrote: > Oh, I also forgot to mention, the polynomial sizes are sizes of polys > a and b where we are factoring a*b. So roughly speaking you should > double the bitsizes and poly lengths if you want the sizes of the > polys being factored. I made no attempt to ensure a and b are > irreducible, so they may have factors themselves. > > Bill. > > On 20 Dec, 02:39, Bill Hart <[EMAIL PROTECTED]> wrote: > > > 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/fact... > > > 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/ -~----------~----~----~----~------~----~------~--~---
