[clean-list] Nested loops and FFT implementation
Jerzy Karczmarczuk
karczma@info.unicaen.fr
Mon, 27 Nov 2000 14:05:45 +0000
Siegfried Gonzi wrote:
> I have a paper which discusses the implementaion of the FFT in functional
> languages. But:
> a) the FFT implementaion via lists is impossible to unterstand
> (the FFT itself is not easy to grasp; Cooley&Tookey with loops is
> most clear).
Oh, yes?
This is a matter of individual appreciation. I often teach FFT
beginning with lists, just plain recursion, BECAUSE IT IS EASIER
TO UNDERSTAND.
And I have plenty of evedence for that, believe me.
fft l z = // where z=exp(2 pi i/N),m length of l is N=2^L
separate l into l1 and l2, evens and odd
compute r1 = fft l1 z^2; r2 = fft l2 z^2
perform the "butterfly recombination", the left half of the
answer r is the sum of r1 and r2 modified by factors z^k,
and the right half is the difference.
3 mathematical formulae in 3 lines.
A code of 6 lines. This code maps *exactly* the formulae.
This is difficult to understand?
Then, of course, some problems appear, and some solutions seem nice,
if instead of lists you use tables. For example, pushing the odd/even
separation down gives you the bit-reversal manipulation which becomes
the preamble. The butterflies may be processed bottom-up, and then
even if instead of squaring z you take the square root which is slower,
the algorithm becomes more stable numerically.
But all this are "goodies". The idea *is functional*.
Jerzy Karczmarczuk