Struct rustfft::algorithm::GoodThomasAlgorithm

pub struct GoodThomasAlgorithm<T> { /* fields omitted */ }

Implementation of the Good-Thomas Algorithm (AKA Prime Factor Algorithm)

This algorithm factors a size n FFT into n1 * n2, where GCD(n1, n2) == 1

Conceptually, this algorithm is very similar to the Mixed-Radix FFT, except because GCD(n1, n2) == 1 we can do some number theory trickery to reduce the number of floating-point multiplications and additions

// Computes a forward FFT of size 1200, using the Good-Thomas Algorithm
use rustfft::algorithm::GoodThomasAlgorithm;
use rustfft::{FFT, FFTplanner};
use rustfft::num_complex::Complex;
use rustfft::num_traits::Zero;

let mut input:  Vec<Complex<f32>> = vec![Zero::zero(); 1200];
let mut output: Vec<Complex<f32>> = vec![Zero::zero(); 1200];

// we need to find an n1 and n2 such that n1 * n2 == 1200 and GCD(n1, n2) == 1
// n1 = 48 and n2 = 25 satisfies this
let mut planner = FFTplanner::new(false);
let inner_fft_n1 = planner.plan_fft(48);
let inner_fft_n2 = planner.plan_fft(25);

// the good-thomas FFT length will be inner_fft_n1.len() * inner_fft_n2.len() = 1200
let fft = GoodThomasAlgorithm::new(inner_fft_n1, inner_fft_n2);
fft.process(&mut input, &mut output);

Methods

impl<T: FFTnum> GoodThomasAlgorithm<T>

fn new(n1_fft: Arc<FFT<T>>, n2_fft: Arc<FFT<T>>) -> Self

Creates a FFT instance which will process inputs/outputs of size n1_fft.len() * n2_fft.len()

GCD(n1.len(), n2.len()) must be equal to 1

Trait Implementations

impl<T: FFTnum> FFT<T> for GoodThomasAlgorithm<T>

fn process(&self, input: &mut [Complex<T>], output: &mut [Complex<T>])

Computes an FFT on the input buffer and places the result in the output buffer.

fn process_multi(&self, input: &mut [Complex<T>], output: &mut [Complex<T>])

Divides the input and output buffers into self.len() chunks, then computes an FFT on each chunk.

impl<T> Length for GoodThomasAlgorithm<T>

fn len(&self) -> usize

The FFT size that this algorithm can process

impl<T> IsInverse for GoodThomasAlgorithm<T>

fn is_inverse(&self) -> bool

Returns false if this instance computes forward FFTs, true for inverse FFTs