Computational Complexity
According to Computational complexity theory, computing a set of DFT terms using applications of the Goertzel algorithm on a data set with values with a "cost per operation" of has a complexity order
- To compute a single DFT bin for a complex input sequence of length, the Goertzel algorithm requires multiplications and additions/subtractions within the loop, as well as 4 multiplications and 4 final additions/subtractions, for a total of multiplications and additions/subtractions. This is repeated for each of the frequencies.
In contrast, using an FFT on a data set with values has a complexity order
- This is harder to apply directly because it depends on the FFT algorithm used, but a typical example is a radix-2 FFT, which requires multiplications and additions/subtractions per DFT bin, for each of the bins.
In the complexity order expressions, when the number of calculated terms is smaller than, the advantage of the Goertzel algorithm is clear. But because FFT code is comparatively very complex, the "cost per unit of work" factor is often much larger for an FFT, and the practical advantage favours the Goertzel algorithm more than the complexity expressions indicate.
As a rule-of-thumb for determining whether a radix-2 FFT or a Goertzel algorithm is more efficient, adjust the number of terms N in the data set upward to the nearest exact power of 2, calling this, and the Goertzel algorithm is likely to be faster if
FFT implementations and processing platforms have a significant impact on the relative performance. Some FFT implementations perform internal complex-number calculations to generate coefficients on-the-fly, significantly increasing their "cost K per unit of work." FFT and DFT algorithms can use tables of pre-computed coefficient values for better numerical efficiency, but this requires more accesses to coefficient values buffered in external memory, which can lead to increased cache contention that counters some of the numerical advantage.
Both algorithms gain approximately a factor of 2 efficiency when using real-valued rather than complex-valued input data. However, these gains are natural for the Goertzel algorithm but will not be achieved for the FFT without using certain algorithm variants specialised for transforming real-valued data.
Read more about this topic: Goertzel Algorithm
Famous quotes containing the word complexity:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)