one-indexed-vec 0.2.0

A one-based (1-indexed) wrapper around Vec<T>: element at position N is accessed via vec[N].
Documentation
//! Discrete and Fast Fourier transform.

use crate::Vec1;

#[cfg(not(feature = "std"))]
use alloc::vec::Vec;

#[cfg(feature = "std")]
use std::vec::Vec;

/// A complex number stored as `(real, imaginary)`.
pub type Complex = (f64, f64);

// ============================================================================
// Methods on Vec1<f64>
// ============================================================================

impl Vec1<f64> {
    /// Discrete Fourier transform, O(N²).
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    ///
    /// let s = vec1![1.0, 1.0, 1.0, 1.0];
    /// let x = s.dft();
    /// assert!((x[1].0 - 4.0).abs() < 1e-10);
    /// ```
    pub fn dft(&self) -> Vec1<Complex> {
        let n = self.len();
        let mut out = Vec1::with_capacity(n);
        for k in 1..=n {
            let mut re = 0.0;
            let mut im = 0.0;
            for i in 1..=n {
                let angle = -2.0 * core::f64::consts::PI * ((k - 1) * (i - 1)) as f64 / n as f64;
                re += self[i] * libm::cos(angle);
                im += self[i] * libm::sin(angle);
            }
            out.push((re, im));
        }
        out
    }
}

// ============================================================================
// Methods on Vec1<Complex>
// ============================================================================

impl Vec1<Complex> {
    /// Inverse DFT, O(N²).
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    ///
    /// let s = vec1![1.0, 2.0, 3.0, 4.0];
    /// let x = s.dft();
    /// let back = x.idft();
    /// for i in 1..=4 {
    ///     assert!((s[i] - back[i]).abs() < 1e-10);
    /// }
    /// ```
    pub fn idft(&self) -> Vec1<f64> {
        let n = self.len();
        let mut out = Vec1::with_capacity(n);
        for i in 1..=n {
            let mut v = 0.0;
            for k in 1..=n {
                let angle = 2.0 * core::f64::consts::PI * ((k - 1) * (i - 1)) as f64 / n as f64;
                let (re, im) = self[k];
                v += re * libm::cos(angle) - im * libm::sin(angle);
            }
            out.push(v / n as f64);
        }
        out
    }

    /// Iterative radix-2 Cooley-Tukey FFT.
    ///
    /// Length must be a power of two.
    ///
    /// ```rust
    /// use one_indexed_vec::{vec1, Vec1};
    ///
    /// let s = vec1![1.0, 2.0, 3.0, 4.0];
    /// let d = s.dft();
    /// let sc: Vec1<(f64, f64)> = vec1![(1.0, 0.0), (2.0, 0.0), (3.0, 0.0), (4.0, 0.0)];
    /// let f = sc.fft();
    /// for k in 1..=4 {
    ///     assert!((d[k].0 - f[k].0).abs() < 1e-10);
    /// }
    /// ```
    pub fn fft(&self) -> Vec1<Complex> {
        let n = self.len();
        assert!(n.is_power_of_two(), "fft: length must be a power of two");

        let mut buf: Vec<Complex> = (1..=n).map(|i| self[i]).collect();

        // Bit-reversal permutation.
        let mut j = 0usize;
        for i in 0..n {
            if i < j {
                buf.swap(i, j);
            }
            let mut m = n >> 1;
            while m >= 1 && j >= m {
                j -= m;
                m >>= 1;
            }
            j += m;
        }

        // Butterflies.
        let mut len = 2;
        while len <= n {
            let ang = -2.0 * core::f64::consts::PI / len as f64;
            let (wr, wi) = (libm::cos(ang), libm::sin(ang));
            let half = len / 2;
            let mut i = 0;
            while i < n {
                let mut cur = (1.0, 0.0);
                for k in 0..half {
                    let (ur, ui) = buf[i + k];
                    let (vr, vi) = buf[i + k + half];
                    let tr = cur.0 * vr - cur.1 * vi;
                    let ti = cur.0 * vi + cur.1 * vr;
                    buf[i + k] = (ur + tr, ui + ti);
                    buf[i + k + half] = (ur - tr, ui - ti);
                    let nr = cur.0 * wr - cur.1 * wi;
                    let ni = cur.0 * wi + cur.1 * wr;
                    cur = (nr, ni);
                }
                i += len;
            }
            len <<= 1;
        }

        let mut out = Vec1::with_capacity(n);
        for v in buf {
            out.push(v);
        }
        out
    }

    /// Magnitude spectrum `|X_k|`.
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    ///
    /// let spec = vec1![(3.0, 4.0), (0.0, 0.0)];
    /// let mag = spec.magnitude();
    /// assert!((mag[1] - 5.0).abs() < 1e-10);
    /// ```
    pub fn magnitude(&self) -> Vec1<f64> {
        let mut out = Vec1::with_capacity(self.len());
        for i in 1..=self.len() {
            let (re, im) = self[i];
            out.push(libm::sqrt(re * re + im * im));
        }
        out
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::vec1;

    #[test]
    fn dft_constant_signal() {
        let s = vec1![1.0, 1.0, 1.0, 1.0];
        let x = s.dft();
        assert!((x[1].0 - 4.0).abs() < 1e-10);
        assert!(x[1].1.abs() < 1e-10);
    }

    #[test]
    fn fft_matches_dft() {
        let s = vec1![1.0, 2.0, 3.0, 4.0];
        let d = s.dft();
        let sc: Vec1<Complex> = (1..=s.len()).map(|i| (s[i], 0.0)).collect();
        let f = sc.fft();
        for k in 1..=s.len() {
            assert!((d[k].0 - f[k].0).abs() < 1e-10);
            assert!((d[k].1 - f[k].1).abs() < 1e-10);
        }
    }

    #[test]
    fn idft_roundtrip() {
        let s = vec1![1.0, 2.0, 3.0, 4.0];
        let x = s.dft();
        let back = x.idft();
        for i in 1..=s.len() {
            assert!((s[i] - back[i]).abs() < 1e-10);
        }
    }

    #[test]
    fn magnitude_basic() {
        let spec = vec1![(3.0, 4.0), (0.0, 0.0)];
        let mag = spec.magnitude();
        assert!((mag[1] - 5.0).abs() < 1e-10);
        assert!((mag[2] - 0.0).abs() < 1e-10);
    }
}