Yes, that works for me. I just don't know how to use MAGMA.
Here is the script I used:
a:=[1 .. 255 by 1];
b:=[1 .. 255 by 1];
for i:=1 to 1000 do
for j:= 1 to 255 do
a[j]:=RandomBits(1000);
b[j]:=RandomBits(1000);
end for;
temp:=Polynomial(a)*Polynomial(b);
end for;
I still don't see why that
On Fri, 20 Oct 2006, Bill Hart wrote:
> I can't get MAGMA to go that fast.
>
> I timed it doing 1000 multiplies of degree 255 polynomials with
> coefficients of 1000 bits. It took 15 seconds or thereabouts.
I'm getting 3.7 seconds with version V2.12-20 and 6.9 seconds with
version V2.13-5. I'
William Stein wrote:
> One other potential issue is that I upgraded MAGMA on sage.math from
> version 2.12-20 to version 2.13-5 since when David did his tests.
> Maybe MAGMA got way slower?!
Frayed Knot. It take about 14-1.5 = 12.5s. Still faster than NTL at
17s, but only marginally so and poss
On Fri, 20 Oct 2006 18:08:42 -0700, Bill Hart <[EMAIL PROTECTED]> wrote:
> I can't get MAGMA to go that fast.
>
> I timed it doing 1000 multiplies of degree 255 polynomials with
> coefficients of 1000 bits. It took 15 seconds or thereabouts.
>
> I timed a similar thing with NTL and it took 17 seco
I can't get MAGMA to go that fast.
I timed it doing 1000 multiplies of degree 255 polynomials with
coefficients of 1000 bits. It took 15 seconds or thereabouts.
I timed a similar thing with NTL and it took 17 seconds. They seem
comparable to me.
The only thing I didn't do is amortize the cost o
OK, I figured it out now. Pari was playing a nasty little trick. It
stops the Karatsuba iteration before it reaches the bottom. It turns
out that this is much faster when the bitlength of the coefficients is
small.
In fact I am now around twice as fast as Pari, unless I have made a
stupid error s
Now this has me confused. Pari uses Karatsuba for multplying
polynomials. It's implementation doesn't look any different to any
other Karatsuba implementation I have seen, except it has some
(irrelevant) tricks for speeding it up when the polynomial is sparse.
But it really does beat NTL by a fac
Bill Hart wrote:
> Anyhow, I'm now wondering whether MAGMA just uses Toom-3 instead of
> Karasuba by the time you get to degree 250 or so. I'll implement a
> Toom-3 algorithm once I get my Karasuba implementation sorted out, and
> we'll see.
Of course I am wrong. NTL runs roughly twice as fast
That could be useful. Thanks.
--~--~-~--~~~---~--~~
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
URL
On Oct 20, 2006, at 9:43 AM, Bill Hart wrote:
> Anyhow, I'm now wondering whether MAGMA just uses Toom-3 instead of
> Karasuba by the time you get to degree 250 or so. I'll implement a
> Toom-3 algorithm once I get my Karasuba implementation sorted out, and
> we'll see.
I believe GMP has mpn-le
10 matches
Mail list logo
