Comment by briansm
1 day ago
It's interesting that in terms of practical implementations, since each multiply can be done as a series of bit-shifts and additions, and since each element of an FFT is just the solution of a polynomial (a series of multiply-accumulates), in theory it's theoretically possible to do a full FFT in a single cpu clock cycle, much as it's possible to do a single multiply or multiply-accumulate in a single clock cycle (via parallel shift-accumulate operations). It would take a ridiculous number of transistors to implement though.
Whether something can be done in a single clock cycle is not useful to know, because this does not say how long is that clock cycle.
A useful performance measure for the evaluation of a function in hardware is the latency of the operation expressed as a multiple of the delay through some standard simple logic gate, e.g. the FO4 delay (of an inverter with a fan-out of 4) that is frequently used in CMOS technology.
While a multiplication can be done in a single clock-cycle if you choose so, the duration of that clock cycle in FO4 delays increases with the size of the numbers that are multiplied, and it is interesting to know how fast it increases with a given multiplication algorithm.
If a multiplication algorithm that claims to be faster when expressed in some abstract operations leads to a FO4 delay number that actually grows faster with the length in bits of the operands, than that algorithm is worse in practice.
There are certainly hardware implementations of FFTs, in high-speed communications systems and the likes. So it's not just theoretical :-)