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. Thus, the cost to
square N become : n/2*log2(n/2)+n/2+n/2*log2(n/2)=n*log2(n)-n/2.
Furthermore, the Discrete Fourier Transform allows to divide the FFt length
by two and perform the mod operation.
Is it possible to combine these two techniques so as to divide the FFT
length by four ?
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
