2 ms·
Well, actually ... Summation is linear time, multiplication is superlinear (eg n log n in number of digits). Meaning that this takes k summations and one multi
by emil-lp 1y ago
Well, actually ... Summation is linear time, multiplication is superlinear (eg n log n in number of digits).
Meaning that this takes k summations and one multiplication rather than k multiplications and k summations.
... Where k is the number of terms.
- ajross 1y ago"Digits" are constant in an FFT (or rather ignored, really, precision is out of scope of the algorithm definition). Obviously in practice these are implemented as (pairs of, for a complex FFT, though real-valued DCTs are much more common) machine words in practice, and modern multipliers and adders pipeline at one per cycle.