I think I finally found the faster algorithm. It's just plain
Schoenhage-Strassen, but with a so called sqrt 2 trick.
Basically, if you want to do a multiplication for polynomials of degree
<= 2^l, you need to do a 2^l point FFT, which means you need to work in
a ring that has 2^l roots of unity.
On Oct 23, 2006, at 10:43 AM, Bill Hart wrote:
> At one stage MAGMA were boasting that their integer multiplication was
> a lot faster than GMP, but I suspect GMP has caught them up now, and I
> think it only made a difference to numbers of a million bits or more.
> MAGMA now seem to claim that
Bill Hart wrote:
> This page apparently answers the question definitively:
>
> http://magma.maths.usyd.edu.au/magma/Features/node93.html
And this paper tells me exactly what I want to know:
http://www.mathematik.hu-berlin.de/~gaggle/EVENTS/2006/BRENT60/presentations/Allan%20Steel%20-%20Reduce%2
This page apparently answers the question definitively:
http://magma.maths.usyd.edu.au/magma/Features/node93.html
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED
William Stein wrote:
> I wonder why they switched from that faster algorithm to a slower one?
> Maybe it produced incorrect results (possibly due to rounding errors)?
I doubt they did. On their website there is no mention in their
changelogs of any change in the algorithm for multiplication of
On Sun, 22 Oct 2006 19:23:00 -0500, Bill Hart <[EMAIL PROTECTED]> wrote:
>> The only thing I'm aware of is the bit-operations I mentioned in an
>> earlier email about his SSMul function.
>
> The thing that really sux is that earlier version of MAGMA computes the
> whole product in less time than N
On Oct 22, 2006, at 6:32 PM, Bill Hart wrote:
> I am now absolutely certain MAGMA uses the FFT for multiplying
> polynomials over ZZ right down to degree 16 (when the bit length is
> 1000). This is a **much** lower cutoff than NTL uses, which is
> indicative of the fact that MAGMA's FFT is way b
David Harvey wrote:
> On Oct 22, 2006, at 6:32 PM, Bill Hart wrote:
>
> > I am now absolutely certain MAGMA uses the FFT for multiplying
> > polynomials over ZZ right down to degree 16 (when the bit length is
> > 1000). This is a **much** lower cutoff than NTL uses, which is
> > indicative of the
