Naessens Yan wrote:
>In this message, I assume FFT are complex FFT and are used to quickly
>square numbers.
>Let N=bp*B^p+...+b2*B^2+b1*B+b0.
>
>You can store the digits b0, b1 ... bp in the real part of a complex signal
>s1 and then apply a FFT on s1. Thus, the cost to square N is :
>n*log2(n)+n+n*log2(n) with n>=2*p.
>But, you can also store the digits b0, b1 ... bp in both real and imaginary
>parts of a complex signal s2 and then apply a FFT on s2.
Yes, that's the standard trick as described in many references (cf.
Numerical Recipes, though I don't recommend their FFT for actual
LL testing work.) Note that many codes instead use a real-signal
variant of the FFT, which avoids the real/complex wrapper steps
(and their (j, N-j) index correlations) of the complex transform
applied to real data.
>Thus, the cost to >square N become :
> n/2*log2(n/2)+n/2+n/2*log2(n/2)=n*log2(n)-n/2.
That's strictly the asymptotic arithmetic opcount. In practice, the
higher-order terms are much less important than the terms that appear
when one factors in cache miss costs and memory latency of actual
computer hardware. If you write really, really good code, you may
approach the n*log(n) behavior for large FFT lengths.
>Furthermore, the Discrete Fourier Transform allows to divide the FFt length
>by two and perform the mod operation.
It's the Crandall/Fagin Discrete Weighted Transform (DWT) that allows
us to do this, not the DFT.
>Is it possible to combine these two techniques so as to divide the FFT
>length by four ?
Yes - all of the good LL test programs do this.
Cheers,
-Ernst
