Taking a look at the actual data from the timings I did, the time
taken to factor varies much more in Magma than in NTL. Here are the
Magma timings for length 341 polynomials:
341 1 1.020e+06 1.723e+06
341 2 9.600e+05 3.090e+06
341 3 1.937e+06 3.177
I fixed the four magma graphs above so that they take into account the
time to compute and divide by the content, since Pari and NTL
certainly do that.
The result is just about the same. Magma is significantly faster for
longer polynomials, usually a factor of about 2.5, though it varies a
bit.
And here we go for generic polynomials:
Magma vs Pari:
http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/magpari-factor-gen.png
Magma vs NTL:
http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/magNTL-factor-gen.png
Bill.
On 20 Dec, 20:13, Bill Hart <[EMAIL PROTEC
On Dec 20, 2007 1:13 PM, Bill Hart <[EMAIL PROTECTED]> wrote:
>
> For comparison, here is our favourite non-free closed source package
> vs Pari and NTL for factoring with two large factors:
>
> Magma vs Pari:
>
> http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/magpari-factor.png
For comparison, here is our favourite non-free closed source package
vs Pari and NTL for factoring with two large factors:
Magma vs Pari:
http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/magpari-factor.png
Magma vs NTL:
http://sage.math.washington.edu/home/wbhart/flint-trunk/gr
I've redone both graphs since the generic NTL profiling code in FLINT
was assuming that a length n polynomial had n+1 coefficients (my
student had done this due to some confusion about the way coefficients
were counted).
The graph for polynomials with two large factors (at least):
http://sage.ma
Here is the graph for generic polynomials:
http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/factor-gen.png
At about 1000 bits and length 6, NTL does seem to get ahead again.
Bill.
--~--~-~--~~~---~--~~
To post to this group, send email to sage-dev
On 20 Dec, 16:22, "Joel B. Mohler" <[EMAIL PROTECTED]> wrote:
> On Thursday 20 December 2007 10:56, Bill Hart wrote:
>
> > Does SAGE use the GP interpreter or the Pari library to do this
> > computation? If it is using the Pari library, and the data conversion
> > isn't quadratic time, then I don'
On Thursday 20 December 2007 10:56, Bill Hart wrote:
> Does SAGE use the GP interpreter or the Pari library to do this
> computation? If it is using the Pari library, and the data conversion
> isn't quadratic time, then I don't think this should be a problem.
The library and I think the conversio
Hi Joel,
Yes, it occurred to me this morning that conversion costs might be
getting in the way.
Does SAGE use the GP interpreter or the Pari library to do this
computation? If it is using the Pari library, and the data conversion
isn't quadratic time, then I don't think this should be a problem.
On Wednesday 19 December 2007 23:42, Bill Hart wrote:
> Here is a graph that uses slightly bigger coefficients, up to 1
> bits.
>
> http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/factor2.pn
>g
>
> I don't see the speed increase you mentioned for large coefficients,
> but this
Here is a graph that uses slightly bigger coefficients, up to 1
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
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 fac
Oops, I mean factoring in ZZ[x].
I should also point out that for any given bitsize and polynomial
length the shortest time is taken in each case. This is of course a
stupid way to time factorisation, but it gives a starting point I
suppose.
Bill.
On 20 Dec, 02:39, Bill Hart <[EMAIL PROTECTED]>
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 polyno
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
On Dec 19, 2007, at 7:19 PM, Bill Hart 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
> implemen
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
a
On 19 Dec, 18:40, "Joel B. Mohler" <[EMAIL PROTECTED]> wrote:
> On Wed, Dec 19, 2007 at 06:03:32PM +, 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
On Wed, Dec 19, 2007 at 06:03:32PM +, 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'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?
John
On 19/12/2007, Joel B. Mohler <[EMAIL PROTECTED]> wrote:
>
> Ticket
>
21 matches
Mail list logo
