Skip to main content

mathverse_complex/
fft.rs

1//! Fast Fourier Transform (radix-2 Cooley–Tukey) and inverse FFT.
2//!
3//! Inputs must have power-of-two length. For the extended transform suite
4//! (real-input FFT, 2D FFT, convolution, …), see `mathverse-transforms`.
5
6use crate::Complex;
7
8/// Radix-2 Cooley–Tukey FFT of `input`.
9///
10/// The length must be a power of two; otherwise this panics.
11///
12/// ```
13/// use mathverse_complex::{fft::fft, Complex};
14/// let x = vec![Complex::new(1.0, 0.0), Complex::new(2.0, 0.0)];
15/// let y = fft(&x);
16/// assert_eq!(y.len(), 2);
17/// assert!((y[0].re - 3.0).abs() < 1e-12);
18/// assert!((y[1].re + 1.0).abs() < 1e-12);
19/// ```
20pub fn fft(input: &[Complex]) -> Vec<Complex> {
21    let n = input.len();
22    assert!(
23        n.is_power_of_two(),
24        "fft: input length must be a power of two, got {n}"
25    );
26    if n <= 1 {
27        return input.to_vec();
28    }
29    let even: Vec<Complex> = input.iter().step_by(2).copied().collect();
30    let odd: Vec<Complex> = input.iter().skip(1).step_by(2).copied().collect();
31    let even_fft = fft(&even);
32    let odd_fft = fft(&odd);
33    let mut result = vec![Complex::zero(); n];
34    for k in 0..n / 2 {
35        let twiddle = Complex::polar(1.0, -2.0 * core::f64::consts::PI * k as f64 / n as f64);
36        let t = twiddle * odd_fft[k];
37        result[k] = even_fft[k] + t;
38        result[k + n / 2] = even_fft[k] - t;
39    }
40    result
41}
42
43/// Inverse FFT: `ifft(fft(x)) ≈ x` (up to floating-point roundoff).
44pub fn ifft(input: &[Complex]) -> Vec<Complex> {
45    let n = input.len();
46    assert!(
47        n.is_power_of_two(),
48        "ifft: input length must be a power of two, got {n}"
49    );
50    let conj: Vec<Complex> = input.iter().map(Complex::conjugate).collect();
51    let mut result = fft(&conj);
52    for c in &mut result {
53        *c = c.conjugate() / Complex::real(n as f64);
54    }
55    result
56}
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn fft_single_element() {
64        let x = vec![Complex::new(3.5, -1.0)];
65        assert_eq!(fft(&x), x);
66        assert!((ifft(&x)[0] - x[0]).norm() < 1e-12);
67    }
68
69    #[test]
70    fn fft_roundtrip() {
71        let x: Vec<Complex> = (0..8)
72            .map(|i| Complex::new((i as f64) * 0.5, (i as f64).sin()))
73            .collect();
74        let y = ifft(&fft(&x));
75        for (a, b) in x.iter().zip(y.iter()) {
76            assert!((a - b).norm() < 1e-12);
77        }
78    }
79
80    #[test]
81    fn fft_matches_dft() {
82        // Brute-force DFT comparison on 4 points
83        let x: Vec<Complex> = (0..4)
84            .map(|i| Complex::new(i as f64, 2.0 * i as f64))
85            .collect();
86        let n = x.len();
87        let dft: Vec<Complex> = (0..n)
88            .map(|k| {
89                (0..n)
90                    .map(|j| {
91                        x[j] * Complex::polar(
92                            1.0,
93                            -2.0 * core::f64::consts::PI * (k * j) as f64 / n as f64,
94                        )
95                    })
96                    .fold(Complex::zero(), |acc, v| acc + v)
97            })
98            .collect();
99        let y = fft(&x);
100        for (a, b) in y.iter().zip(dft.iter()) {
101            assert!((a - b).norm() < 1e-10);
102        }
103    }
104}