I remember from back in my supercomputer days, the FFT algorithm was pretty important in the field I worked in, and there were generally 2 ways to implement it. The first used bit-reverse and radix-2 transform, while the second used digit-reverse and radix-4 transform. Radix-4 was quite a bit faster in implementation, so what I'm wondering is which is the version of the FFT function on the HP Prime, radix-2 or radix-4 ?????????
Thanks
-Donald
I looked through the source code and from what I can tell, in maple.cc, if HP uses gcc and libgsl (Gnu Scientific Library), then they call the radix2 transform function.
Anyway, radix 4 speed increases are only significant when a large number of data elements are being used and since we are talking about a calculator, it's doubtful if large numbers of data elements are going to be used in fft's. Thus the advantage of a radix-4 would be minimal in any case.
Good 'nuff... :-)
Thx
-Donald
The GSL is not active when giac is compiled for the Prime.
There are two main FFT implementations, one for complex<double> data, and one for modular integers. The first one has prototype
Code:
void fft(std::complex<double> * f,int n,const std::complex<double> * w,int m,complex< double> * t)
it first checks if the size is even, if it is odd it tries to find a factor, if not it applies slow FFT. For even size, there is no special code if n is divisible by 4. The implementation for complex<double> is not fully optimized (the integer modular fft is more optimized).