Principle:Avhz RustQuant Fast Fourier Transform

Knowledge Sources	Cooley, Tukey - An Algorithm for the Machine Calculation of Complex Fourier Series Carr, Madan - Option Valuation Using the Fast Fourier Transform
Domains	Numerical_Methods, Signal_Processing
Last Updated	2026-02-07 21:00 GMT

Overview

The Fast Fourier Transform (FFT) is an efficient algorithm for computing the Discrete Fourier Transform, reducing computational complexity from O(n^2) to O(n log n), with applications in signal processing and option pricing via characteristic functions.

Description

The Fast Fourier Transform implementation in RustQuant provides both real-valued and complex-valued FFT computation using the classic Cooley-Tukey radix-2 decimation-in-time algorithm.

The module exposes four primary functions:

• fft_real(x): computes the FFT of a real-valued input vector, returning a new vector of results
• fft_real_inplace(x): computes the FFT of a real-valued vector in place, modifying the input
• fft_complex(x): computes the FFT of a complex-valued input vector, returning a new vector
• fft_complex_inplace(x): computes the FFT of a complex-valued vector in place

All functions require that the input length be a power of 2, which is validated by the is_valid_length helper function. This constraint arises from the radix-2 algorithm's recursive halving strategy.

The implementation uses a recursive divide-and-conquer approach: 1. Split the input into even-indexed and odd-indexed subsequences 2. Recursively compute the FFT of each half 3. Combine the results using twiddle factors $e^{-2\pi ik/n}$

For real-valued FFT, the twiddle factor's magnitude (norm) is used in the combination step, while the complex-valued FFT uses the full complex exponential multiplication.

The complex number support comes from the num::Complex crate, providing precise arithmetic for the Fourier basis functions.

Usage

Use the FFT for spectral analysis of time series data, frequency-domain filtering, and option pricing via characteristic function methods (e.g., the Carr-Madan method for pricing European options under models with known characteristic functions such as Heston or Variance Gamma). The input vector length must be a power of 2; pad with zeros if necessary.

Theoretical Basis

The Discrete Fourier Transform (DFT) of a sequence $x_0,x_1,\dots ,x_{n-1}$ is:

$X_k=\sum _{j=0}^{n-1}{x}_j\cdot e^{-2\pi ijk/n},k=0,1,\dots ,n-1$

The Cooley-Tukey algorithm exploits the periodicity and symmetry of the complex exponential. By separating even and odd indices:

$X_k=\sum _{m=0}^{n/2-1}{x}_{2m}\cdot e^{-2\pi imk/(n/2)}+e^{-2\pi ik/n}\sum _{m=0}^{n/2-1}{x}_{2m+1}\cdot e^{-2\pi imk/(n/2)}$

This can be written as:

$X_k=E_k+W_n^k\cdot O_k$

$X_{k+n/2}=E_k-W_n^k\cdot O_k$

where $E_k$ and $O_k$ are the DFTs of the even and odd subsequences, and $W_n^k=e^{-2\pi ik/n}$ is the twiddle factor. This butterfly operation reduces the $O(n^2)$ DFT to $O(n\log n)$ recursive steps.

Related Pages

Implemented By

• Implementation:Avhz_RustQuant_FFT