Re: Schönhage-Strassen

[David Harvey]

On Aug 31, 2010, at 4:58 AM, Paul Zimmermann wrote:

>        Dear Tsz Wo Sze,
>
>> Date: Mon, 30 Aug 2010 20:48:15 -0700 (PDT)
>> From: Tsz Wo Sze <szetszwo at yahoo.com>
>>
>> Hi Pual and Torbjorn,
>>
>> Thanks for the replies.  How did you achieve 10N+o(N)?
>
> I don't know how Torbjörn gets 10N, but I agree with your calculation:
>
> * we need two buffers of N for the inputs : total 2N
> * we need a buffer of 2N for the output : total 2N
> * we need two buffers of 4N each for the Fourier transforms : total 8N
>   (we reuse one buffer for the inverse transform)
>
> Paul

I suppose you could use the output buffer to store part of the  
fourier transform of one of the inputs, to save 2N?

david