I find quite a lot of information about radix-2, radix-4, split-radix, mixed-radix FFT. There are some mentions here and there that choosing a "base case" for the recursion that is larger than the length-2 FFT (in radix-2), or length-4, etc, can help performance quite a bit. But I have a hard time finding documentation / guidelines about what kind of base case can / should be used, how the corresponding FFT should be formulated, etc. Any advices on this?
3
-
$\begingroup$ Can you provide a source or reference for your quote.? What exactly is the "base case" of an FFT ? $\endgroup$– HilmarCommented Nov 15, 2021 at 21:06
-
$\begingroup$ The FFT algorithms like e.g. radix-2 are often formulated as recursive algorithms, so in this context the base case is the case where the recursion ends. $\endgroup$– Zorglub29Commented Nov 21, 2021 at 18:06
-
$\begingroup$ I see. You can certainly formulate it recursively but practical implementations rarely do. It's less efficient than iterating through the stages. $\endgroup$– HilmarCommented Nov 22, 2021 at 18:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Thanks, will look into it. Btw, this is again an example of this 'writing between the lines' that the base case is 'in theory' for FFT length of size 1, feels like the 'in theory' may suggest that in practice some other base case should be preferred. $\endgroup$ Commented Nov 16, 2021 at 6:38
-
1$\begingroup$ @Zorglub29 Have a look at the second link above. I think the answer is (as always) "it depends": it depends on the data types, it depends on the processor used, etc. etc. :-) $\endgroup$– Peter K. ♦Commented Nov 16, 2021 at 13:00