use crate::Complex;
pub fn fft(input: &[Complex]) -> Vec<Complex> {
let n = input.len();
assert!(
n.is_power_of_two(),
"fft: input length must be a power of two, got {n}"
);
if n <= 1 {
return input.to_vec();
}
let even: Vec<Complex> = input.iter().step_by(2).copied().collect();
let odd: Vec<Complex> = input.iter().skip(1).step_by(2).copied().collect();
let even_fft = fft(&even);
let odd_fft = fft(&odd);
let mut result = vec![Complex::zero(); n];
for k in 0..n / 2 {
let twiddle = Complex::polar(1.0, -2.0 * core::f64::consts::PI * k as f64 / n as f64);
let t = twiddle * odd_fft[k];
result[k] = even_fft[k] + t;
result[k + n / 2] = even_fft[k] - t;
}
result
}
pub fn ifft(input: &[Complex]) -> Vec<Complex> {
let n = input.len();
assert!(
n.is_power_of_two(),
"ifft: input length must be a power of two, got {n}"
);
let conj: Vec<Complex> = input.iter().map(Complex::conjugate).collect();
let mut result = fft(&conj);
for c in &mut result {
*c = c.conjugate() / Complex::real(n as f64);
}
result
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn fft_single_element() {
let x = vec![Complex::new(3.5, -1.0)];
assert_eq!(fft(&x), x);
assert!((ifft(&x)[0] - x[0]).norm() < 1e-12);
}
#[test]
fn fft_roundtrip() {
let x: Vec<Complex> = (0..8)
.map(|i| Complex::new((i as f64) * 0.5, (i as f64).sin()))
.collect();
let y = ifft(&fft(&x));
for (a, b) in x.iter().zip(y.iter()) {
assert!((a - b).norm() < 1e-12);
}
}
#[test]
fn fft_matches_dft() {
let x: Vec<Complex> = (0..4)
.map(|i| Complex::new(i as f64, 2.0 * i as f64))
.collect();
let n = x.len();
let dft: Vec<Complex> = (0..n)
.map(|k| {
(0..n)
.map(|j| {
x[j] * Complex::polar(
1.0,
-2.0 * core::f64::consts::PI * (k * j) as f64 / n as f64,
)
})
.fold(Complex::zero(), |acc, v| acc + v)
})
.collect();
let y = fft(&x);
for (a, b) in y.iter().zip(dft.iter()) {
assert!((a - b).norm() < 1e-10);
}
}
}