Hi!
I've tried the 'new' fft in Maxima with support for lists. While all
is nice and it 'works', after inspecting sourcecode it seem to be
implemented in a very inefficient way. I haven't tested the speed of
the internal fft algorithm, but since it's a lisp rewrite from a
fortran book, probably there are faster algorithms.
What concerns me the most is the conversion from array to a list and
such related tasks.
Code like
(dotimes (i ($length a1))
(setf (nth (1+ i) a1) (m+ (nth (1+ i) a1) (m* '$%i (nth (1
+ i) a2)))))
can't be efficient on lists of length perhaps 1024*8. Surely the list
should be traversed in some other way (and constructing a complex
number with m+ and m* is probably an overkill also). Maxima's 'fft'
is terribly slow, but doesn't need to be.
I would suggest also to take a look at existing implementations in CL
like
Bordeaux-FFT
which also allows for arrays which are not of length of power of 2
(but uses a much slower algorithm in such cases).
Why not use code that's already there in such cases?
Ideally FFTW with CFFI should be used, but since Maxima doesn't want
to rely on C libraries yet, this is not an option.
Regards,
Ziga