On Wed, 15 Nov 2006 19:13:06 -0800, Bill Hart
<[EMAIL PROTECTED]> wrote:
> Also, Pari is not *that* tightly coded. FLINT also implements the
> Karatsuba method for multiplication of polynomials.
>
> I just timed it multiplying 10000 degree 255 polynomials with 1000 bit
> coefficients.
>
> The timing comparison is:
>
> Pari Karatsuba: 295s
> FLINT Karatsuba: 64s
>
> I've checked my code, made certain that the output is actually the same
> as given by the naieve method (which FLINT also implements), did an
> eyeball test to make sure I wasn't returning something that looked
> ridiculous.
>
> Basically, I believe we really can do Karatsuba that fast.
>
> This is even faster than NTL's Schoenhage-Strassen. Hard to believe,
> but I've just spent half an hour trying to disprove myself.
>
> I also don't know why my Pari timings are so much lower than William's
> timing (I used f*(g+i) to prevent cheating). I suggest it has to do
> with wall time versus actual cpu cycles.
I don't use wall time at all for timing pari computations. I used
the gettime. But I'm now getting more reasonable timings for PARI.
Here's the new benchmarks;
MAGMA 28.840s
PARI 134.156s
SAGE 420s (current NTL *wrapper* ?? -- should be 130-ish)
SINGULAR 839s
Maple 2100s
Mathematica 2075s
GAP 2846s (estimate)
Maxima 5000s (estimate)
Here's how I to do the PARI timing:
sage: v = [randint(0,2^1000) for _ in range(256)]
sage: w = [randint(0,2^1000) for _ in range(256)]
sage: R.<x> = PolynomialRing(ZZ)
sage: f = R(v)
sage: g = R(w)
sage: gp.eval('f=%s; g=%s;"";'%(f,g))
'""'
sage: gp.eval('gettime; for(i=1,100,f*(g+i)); gettime')
'1336'
sage: gp.eval('gettime; for(i=1,100,f*(g+i)); gettime/1000.0')
'1.3370000000000000000000000000000000000'
sage: gp.eval('gettime; for(i=1,1000,f*(g+i)); gettime/1000.0')
'13.376000000000000000000000000000000000'
sage: gp.eval('gettime; for(i=1,10000,f*(g+i)); gettime/1000.0')
'134.15600000000000000000000000000000000'
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
