1use crate::Complex;
7
8pub 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
43pub 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 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}