[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