- **Similar:** [IFFT](../ifft/Ifft.md), [CWT](../cwt/Cwt.md) | **Trading note:** Fast Fourier Transform; identifies dominant frequencies/cycles in price data. Foundation of spectral analysis.
The FFT indicator computes the dominant cycle period in a price series using a true radix-2 Cooley-Tukey Fast Fourier Transform with a Hanning window. Rather than outputting frequency-domain magnitudes, it returns the estimated dominant cycle period in bars, making it directly usable as an adaptive period input for other indicators. The implementation uses an in-place iterative radix-2 FFT with bit-reversal permutation and Cooley-Tukey butterfly operations, achieving $O(N \log N)$ complexity. Parabolic interpolation on the magnitude spectrum provides sub-bin frequency resolution. With window sizes restricted to powers of two (32, 64, or 128), the indicator achieves precise cycle detection within user-specified period bounds with pre-allocated work arrays for zero-allocation streaming.
The Fourier transform, formalized by Joseph Fourier (1822), decomposes any periodic signal into sinusoidal components. The Fast Fourier Transform algorithm, published by James Cooley and John Tukey in 1965, reduced the DFT from $O(N^2)$ to $O(N \log N)$ by recursively decomposing the DFT into smaller sub-problems using the "butterfly" operation pattern. The radix-2 variant requires power-of-two input lengths and uses bit-reversal permutation followed by iterative butterfly stages.
John Ehlers pioneered the application of spectral analysis to financial markets in the 1990s and 2000s, using FFT-based cycle measurement to create adaptive indicators. His work demonstrated that financial time series contain quasi-periodic cycles with time-varying periods, typically in the 6-40 bar range. The dominant cycle period, extracted via spectral peak detection, can drive adaptive moving averages (MAMA, FAMA), adaptive RSI, and other indicators that benefit from knowing the current market rhythm.
The Hanning window (also called Hann window, after Julius von Hann) is applied to reduce spectral leakage. Without windowing, the sharp truncation of a finite data segment creates artificial high-frequency components that contaminate the spectrum. The Hanning window tapers the data to zero at both ends, suppressing sidelobes at the cost of slightly wider main lobes (reduced frequency resolution).
**Stage 2: Bit-reversal permutation** reorders the windowed data according to the bit-reversed indices, preparing for in-place butterfly computation. The permutation table is pre-computed in the constructor.
**Stage 3: Cooley-Tukey butterflies** perform $\log_2(N)$ stages of butterfly operations. Each stage $s$ processes pairs of elements separated by $2^{s-1}$ positions, combining them with twiddle factors:
**Stage 4: Peak detection with parabolic interpolation** finds the bin $k^*$ with maximum squared magnitude in `[minBin, maxBin]`, then refines using a three-point parabolic fit:
**Window size trade-offs**: $N = 32$ gives coarse resolution (period bins spaced ~1 bar apart) but fast response; $N = 128$ gives fine resolution (~0.25 bar spacing) but sluggish adaptation. The default $N = 64$ balances resolution and responsiveness.
## Mathematical Foundation
The **Discrete Fourier Transform** for $N$ samples:
$$X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j 2\pi k n / N}, \quad k = 0, 1, \ldots, N-1$$
O(N log N) per bar. Pre-allocated work arrays ensure zero allocation in the hot path. Twiddle factor computation dominates; pre-computing sin/cos tables would reduce to ~2500 cy.
Moderate SIMD potential: butterfly FMA operations are vectorizable within each stage. Bit-reversal permutation is inherently scalar. Expected 2× speedup over scalar for N=64.
