On 8/22/09, ?iga Lenar?i? <ziga.lenarcic at gmail.com> wrote:
> 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 faster algorithm would that be?
> (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).
Surely indeed. If you would like to suggest an alternative
(i.e. post a patch) I am willing to consider it.
> Maxima's 'fft' is terribly slow, but doesn't need to be.
Well, a claim like this would be a lot stronger if accompanied
by some evidence or argument from first principals or something.
> 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).
Yes, an function to handle cases other than length = 2^n would
be a welcome addition. If you'd like to spell out how to do it
(i.e. post patches & details about how this whole business with
Bordeaux-FFT is going to work) then I'm willing to consider it.
FWIW
Robert Dodier