Fourier Transform vs Goertzel Algorithm for Trading

The Fast Fourier Transform (FFT) and Goertzel algorithm both decompose price signals into frequency components, but they differ in how they allocate computation. FFT computes power at all frequencies simultaneously in O(N log N) time, making it efficient for broad-spectrum exploration. Modern implementations like FFTW handle any sample length at O(N log N), with peak speed at smooth-prime products of the form 2^a · 3^b · 5^c · 7^d (with optional 11 or 13 factor). The Goertzel algorithm computes power at individual target frequencies in O(N) time per frequency, making it more efficient when K (the number of target frequencies) is small relative to log₂ N. For market cycle analysis, where the relevant frequency range (10–300 bars) is known in advance and fractional periods matter, Goertzel provides targeted detection with exact period resolution.

FFT vs Goertzel at a Glance

FFT Overview

The FFT computes the Discrete Fourier Transform efficiently, producing power estimates for all frequencies simultaneously. Given N data points, you get N/2 frequency bins in one computation.

Advantages:

• Complete spectrum in one pass
• Highly optimized implementations available
• Good for exploratory analysis

Disadvantages:

• Computes many frequencies you do not need
• Frequency resolution tied to sample length
• Quantises target frequencies to bin width (FFT bin grid)

Note on sample length: modern libraries like FFTW handle arbitrary lengths at O(N log N), with peak speed at smooth-prime products (2^a · 3^b · 5^c · 7^d). Power-of-2 is no longer a hard requirement, just the canonical fastest case.

Goertzel Overview

Goertzel computes power at specific target frequencies individually. It is mathematically equivalent to computing a single bin of the DFT.

Advantages:

• Efficient when you need only specific frequencies
• Works with any sample size
• Stable for typical block sizes; Reinsch variant available for high-precision use
• Easy to implement (~10 lines)
• Computes any period exactly, including fractional values like 23.5 bars (generalised Goertzel, Sysel & Rajmic 2012)

Disadvantages:

• Must specify which frequencies to calculate
• Slower than FFT if you need many frequencies
• Does not give full spectrum view

Computational Comparison

The asymptotic crossover sits where K equals log₂ N, where K is the number of target frequencies and N is the sample length. The comparison is K · O(N) for Goertzel vs O(N log N) for FFT. In practice, FFT carries larger constant factors per bin than Goertzel does per frequency, so Goertzel's practical advantage extends further than asymptotic theory predicts.

• Goertzel asymptotically faster: K below log₂ N. For a typical cycle-analysis sample of N = 512, that is K under about 9.
• Practical Goertzel zone: per Wikipedia, FFT's constant factors mean Goertzel often remains competitive "for M several times larger than log₂ N", especially for the implementation simplicity it provides.
• FFT clearly faster: K well above log₂ N, e.g. full-spectrum sweeps with hundreds of bins, where FFT amortises across all of them.

For trading cycle detection, you typically scan 20-50 frequencies (e.g., periods from 10 to 100 bars). This sits past the asymptotic crossover but inside the practical zone where constant-factor advantages keep Goertzel competitive. The gap is small on modern hardware. Choose based on convenience and on the other factors below: exact period resolution, sample-length flexibility, and implementation simplicity.

When FFT Is Better

Use FFT when:

• You want to see the complete frequency spectrum
• You are exploring data without preconceptions about which cycles exist
• Sample size is a smooth-prime product (2^a, 3^b, 5^c, etc.) for peak efficiency
• You are analyzing many instruments and need batch efficiency

When Goertzel Is Better

Use Goertzel when:

• You know which frequency range to scan (K is small relative to log₂ N)
• You want exact fractional periods like 23.5 or 41.7 bars (Goertzel computes them directly; FFT quantises to bin width)
• You are implementing from scratch (simpler algorithm, ~10 lines)
• You want specific periods like 20, 40, 60 bars without bin alignment

Practical Recommendation

For trading applications, Goertzel often makes more sense:

1. You typically know the cycle range of interest (e.g., 10-200 bars)
2. You want specific periods, not arbitrary frequency bins
3. Fractional periods matter and bin quantisation is a real loss
4. Implementation is simpler and less error-prone

At FractalCycles, we use Goertzel for production cycle detection. It gives us exactly the frequencies we care about without the overhead of computing the full spectrum.

Hybrid Approach

Some systems use both:

1. FFT for initial exploration: scan the full spectrum to identify interesting regions
2. Goertzel for focused analysis: compute precise power at specific target periods
3. FFT for visualization: show users the complete power spectrum
4. Goertzel for trading logic: efficient calculation of key cycles

This leverages the strengths of each method.

Implementation Notes

If implementing yourself:

• FFT: Use a library (NumPy, FFTW). Do not write your own FFT.
• Goertzel: Simple enough to implement correctly. About 10 lines of code.

Both methods benefit from detrending the data first. Apply to log returns or detrended prices, not raw price levels.