use std::f64::consts::PI;
use ndarray::Array2;
#[derive(Clone, Copy)]
struct Cx {
re: f64,
im: f64,
}
impl Cx {
const ZERO: Cx = Cx { re: 0.0, im: 0.0 };
#[inline]
fn new(re: f64, im: f64) -> Self {
Cx { re, im }
}
#[inline]
fn add(self, o: Cx) -> Cx {
Cx::new(self.re + o.re, self.im + o.im)
}
#[inline]
fn sub(self, o: Cx) -> Cx {
Cx::new(self.re - o.re, self.im - o.im)
}
#[inline]
fn mul(self, o: Cx) -> Cx {
Cx::new(
self.re * o.re - self.im * o.im,
self.re * o.im + self.im * o.re,
)
}
#[inline]
fn conj(self) -> Cx {
Cx::new(self.re, -self.im)
}
#[inline]
fn scale(self, s: f64) -> Cx {
Cx::new(self.re * s, self.im * s)
}
}
fn fft_pow2(a: &mut [Cx]) {
let n = a.len();
debug_assert!(n.is_power_of_two());
let mut j = 0usize;
for i in 1..n {
let mut bit = n >> 1;
while j & bit != 0 {
j ^= bit;
bit >>= 1;
}
j |= bit;
if i < j {
a.swap(i, j);
}
}
let mut len = 2;
while len <= n {
let ang = -2.0 * PI / len as f64;
let wlen = Cx::new(ang.cos(), ang.sin());
let half = len / 2;
let mut i = 0;
while i < n {
let mut w = Cx::new(1.0, 0.0);
for k in 0..half {
let u = a[i + k];
let v = a[i + k + half].mul(w);
a[i + k] = u.add(v);
a[i + k + half] = u.sub(v);
w = w.mul(wlen);
}
i += len;
}
len <<= 1;
}
}
fn ifft_pow2(a: &mut [Cx]) {
for c in a.iter_mut() {
*c = c.conj();
}
fft_pow2(a);
let s = 1.0 / a.len() as f64;
for c in a.iter_mut() {
*c = c.conj().scale(s);
}
}
fn fft_bluestein(x: &[Cx]) -> Vec<Cx> {
let n = x.len();
let mut m = 1usize;
while m < 2 * n - 1 {
m <<= 1;
}
let two_n = 2 * n as u128;
let mut wk = vec![Cx::ZERO; n];
let mut a = vec![Cx::ZERO; m];
for k in 0..n {
let kk = ((k as u128 * k as u128) % two_n) as f64;
let ang = -PI * kk / n as f64;
wk[k] = Cx::new(ang.cos(), ang.sin());
a[k] = x[k].mul(wk[k]);
}
let mut b = vec![Cx::ZERO; m];
b[0] = wk[0].conj();
for k in 1..n {
let bk = wk[k].conj();
b[k] = bk;
b[m - k] = bk;
}
fft_pow2(&mut a);
fft_pow2(&mut b);
for i in 0..m {
a[i] = a[i].mul(b[i]);
}
ifft_pow2(&mut a);
(0..n).map(|k| wk[k].mul(a[k])).collect()
}
fn fft(x: &[Cx]) -> Vec<Cx> {
let n = x.len();
if n == 0 {
return Vec::new();
}
if n.is_power_of_two() {
let mut a = x.to_vec();
fft_pow2(&mut a);
a
} else {
fft_bluestein(x)
}
}
fn ifft(x: &[Cx]) -> Vec<Cx> {
let n = x.len();
if n == 0 {
return Vec::new();
}
let conj: Vec<Cx> = x.iter().map(|c| c.conj()).collect();
let f = fft(&conj);
let s = 1.0 / n as f64;
f.iter().map(|c| c.conj().scale(s)).collect()
}
pub(crate) fn filter_real_column(col: &[f64], d: &[f64]) -> Vec<f64> {
let n = col.len();
if n == 0 {
return Vec::new();
}
let cx: Vec<Cx> = col.iter().map(|&v| Cx::new(v, 0.0)).collect();
let spec = fft(&cx);
let filtered: Vec<Cx> = spec.iter().zip(d).map(|(c, &dv)| c.scale(dv)).collect();
ifft(&filtered).iter().map(|c| c.re).collect()
}
pub(crate) fn filter_real_2d(input: &Array2<f64>, mult: &Array2<f64>) -> Array2<f64> {
let (nrow, ncol) = input.dim();
if nrow == 0 || ncol == 0 {
return Array2::zeros((nrow, ncol));
}
let mut grid: Array2<Cx> = input.mapv(|v| Cx::new(v, 0.0));
for mut lane in grid.rows_mut() {
let f = fft(&lane.iter().copied().collect::<Vec<_>>());
for (dst, src) in lane.iter_mut().zip(f) {
*dst = src;
}
}
for mut lane in grid.columns_mut() {
let f = fft(&lane.iter().copied().collect::<Vec<_>>());
for (dst, src) in lane.iter_mut().zip(f) {
*dst = src;
}
}
grid.zip_mut_with(mult, |g, &m| *g = g.scale(m));
for mut lane in grid.columns_mut() {
let f = ifft(&lane.iter().copied().collect::<Vec<_>>());
for (dst, src) in lane.iter_mut().zip(f) {
*dst = src;
}
}
let mut out = Array2::<f64>::zeros((nrow, ncol));
for (mut orow, glane) in out.rows_mut().into_iter().zip(grid.rows()) {
let f = ifft(&glane.iter().copied().collect::<Vec<_>>());
for (dst, src) in orow.iter_mut().zip(f) {
*dst = src.re;
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
fn dft_naive(x: &[Cx]) -> Vec<Cx> {
let n = x.len();
let nf = n as f64;
(0..n)
.map(|k| {
let mut acc = Cx::ZERO;
for (m, &xv) in x.iter().enumerate() {
let ang = -2.0 * PI * (k as f64) * (m as f64) / nf;
acc = acc.add(xv.mul(Cx::new(ang.cos(), ang.sin())));
}
acc
})
.collect()
}
fn make(seed: u64, n: usize) -> Vec<Cx> {
let mut s = seed;
let mut next = || {
s = s
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
((s >> 33) as f64 / (1u64 << 31) as f64) - 1.0
};
(0..n).map(|_| Cx::new(next(), next())).collect()
}
#[test]
fn fft_matches_naive_dft_all_lengths() {
for &n in &[1usize, 2, 3, 5, 7, 8, 11, 16, 17, 31, 64, 105, 128, 257] {
let x = make(n as u64 + 1, n);
let f = fft(&x);
let r = dft_naive(&x);
let err = f.iter().zip(&r).fold(0.0f64, |m, (a, b)| {
m.max((a.re - b.re).abs().max((a.im - b.im).abs()))
});
let scale = r
.iter()
.fold(1e-300f64, |m, c| m.max(c.re.abs().max(c.im.abs())));
assert!(err / scale < 1e-11, "n={n}: rel err {}", err / scale);
}
}
#[test]
fn ifft_inverts_fft() {
for &n in &[1usize, 3, 5, 8, 17, 105, 128] {
let x = make(n as u64 + 99, n);
let back = ifft(&fft(&x));
let err = x.iter().zip(&back).fold(0.0f64, |m, (a, b)| {
m.max((a.re - b.re).abs().max((a.im - b.im).abs()))
});
assert!(err < 1e-11, "n={n}: round-trip err {err}");
}
}
#[test]
fn filter_real_column_matches_direct() {
for &n in &[6usize, 11, 64, 105] {
let col: Vec<f64> = (0..n)
.map(|i| (i as f64 * 0.37).sin() + 0.1 * i as f64)
.collect();
let d: Vec<f64> = (0..n)
.map(|k| 1.0 - (-((k as f64) - 3.0).powi(2) / 8.0).exp())
.collect();
let cx: Vec<Cx> = col.iter().map(|&v| Cx::new(v, 0.0)).collect();
let spec = dft_naive(&cx);
let g: Vec<Cx> = spec.iter().zip(&d).map(|(c, &dv)| c.scale(dv)).collect();
let gc: Vec<Cx> = g.iter().map(|c| c.conj()).collect();
let inv = dft_naive(&gc);
let nf = n as f64;
let want: Vec<f64> = inv.iter().map(|c| c.conj().scale(1.0 / nf).re).collect();
let got = filter_real_column(&col, &d);
let err = got
.iter()
.zip(&want)
.fold(0.0f64, |m, (a, b)| m.max((a - b).abs()));
assert!(err < 1e-11, "n={n}: filter err {err}");
}
}
#[test]
fn filter_real_2d_matches_naive() {
use ndarray::Array2;
let inv = |v: &[Cx]| -> Vec<Cx> {
let conj: Vec<Cx> = v.iter().map(|c| c.conj()).collect();
let f = dft_naive(&conj);
let s = 1.0 / v.len() as f64;
f.iter().map(|c| c.conj().scale(s)).collect()
};
for &(nr, nc) in &[(4usize, 6usize), (5, 5), (8, 3), (7, 9)] {
let mut mat = Array2::<f64>::zeros((nr, nc));
let mut mult = Array2::<f64>::zeros((nr, nc));
for ((r, c), cell) in mat.indexed_iter_mut() {
*cell = ((r * 7 + c * 3) as f64 * 0.21).sin() + 0.05 * (r + c) as f64;
mult[[r, c]] =
1.0 - (-((r as f64 - 1.5).powi(2) + (c as f64 - 2.0).powi(2)) / 5.0).exp();
}
let mut g: Array2<Cx> = mat.mapv(|v| Cx::new(v, 0.0));
for mut lane in g.rows_mut() {
let f = dft_naive(&lane.iter().copied().collect::<Vec<_>>());
for (dst, src) in lane.iter_mut().zip(f) {
*dst = src;
}
}
for mut lane in g.columns_mut() {
let f = dft_naive(&lane.iter().copied().collect::<Vec<_>>());
for (dst, src) in lane.iter_mut().zip(f) {
*dst = src;
}
}
g.zip_mut_with(&mult, |gv, &m| *gv = gv.scale(m));
for mut lane in g.columns_mut() {
let f = inv(&lane.iter().copied().collect::<Vec<_>>());
for (dst, src) in lane.iter_mut().zip(f) {
*dst = src;
}
}
let mut want = Array2::<f64>::zeros((nr, nc));
for (mut wrow, glane) in want.rows_mut().into_iter().zip(g.rows()) {
let f = inv(&glane.iter().copied().collect::<Vec<_>>());
for (dst, src) in wrow.iter_mut().zip(f) {
*dst = src.re;
}
}
let got = filter_real_2d(&mat, &mult);
let err = want
.iter()
.zip(got.iter())
.fold(0.0f64, |m, (a, b)| m.max((a - b).abs()));
assert!(err < 1e-11, "({nr},{nc}): 2d filter err {err}");
}
}
}