in one of my question about non $ 2^L $ points FFT I got answer with advice to read about that in following book: Rabiner, Lawrence R., and Bernard Gold. "Theory and application of digital signal processing." Englewood Cliffs, NJ, Prentice-Hall, Inc., 1975. 777 p. (1975).
I read that and I found that equation:
There was also explanation how to calculate it, but I could’t understand it - probably because my lack both of English language and math at all.
I was wondering long time what’s the deal with that equation. Let’s say for example I have N=36 point DFT. And make matrix 3x12. There are in equation 4 variables s, r, m, l. So I still need make calculations for each s (which goes from 0 to 11), for each r (from 0 to 2), for each m (0 to 11) and for each l (0 to 2). So it looks like I need to make $ 12 \cdot 3\cdot12 \cdot 3 $ operations. So it’s $ 36^2 $, the same as regular DFT. So where is the deal, where is that FFT efficiency?
But now after some considerations, testing and thinking. I see I can calculate at first:
So for each m (0 to 11), each l (0 to 2) and each s (0 to 2) it gives me $ 12 \cdot 3 \cdot 3 $ calculations. And then I need to calculate that:
and for each m, s and r (0 to 11) I need $ 12 \cdot 3 \cdot 12 $ calculations. And then I need multiply each result by each result from previous equation. So it’s $ (12 \cdot 3 \cdot 12)+(12 \cdot 3 \cdot 3) $ which is equal 540, and it’s much less than $ 36 \cdot 36 $. And is it that deal? I am not sure of my way of thinking. Please could anyone help me with understanding it?