Struct GoodThomasAlgorithmSmall

pub struct GoodThomasAlgorithmSmall<T> { /* private fields */ }

Implementation of the Good-Thomas Algorithm, specialized for smaller input sizes

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

Conceptually, this algorithm is very similar to MixedRadix, except because GCD(n1, n2) == 1 we can do some number theory trickery to reduce the number of floating point operations. It typically performs better than MixedRadixSmall, especially at the smallest sizes.

// Computes a forward FFT of size 56 using GoodThomasAlgorithmSmall
use std::sync::Arc;
use rustfft::algorithm::GoodThomasAlgorithmSmall;
use rustfft::algorithm::butterflies::{Butterfly7, Butterfly8};
use rustfft::{Fft, FftDirection};
use rustfft::num_complex::Complex;

let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 56];

// we need to find an n1 and n2 such that n1 * n2 == 56 and GCD(n1, n2) == 1
// n1 = 7 and n2 = 8 satisfies this
let inner_fft_n1 = Arc::new(Butterfly7::new(FftDirection::Forward));
let inner_fft_n2 = Arc::new(Butterfly8::new(FftDirection::Forward));

// the good-thomas FFT length will be inner_fft_n1.len() * inner_fft_n2.len() = 56
let fft = GoodThomasAlgorithmSmall::new(inner_fft_n1, inner_fft_n2);
fft.process(&mut buffer);

Implementations

impl<T: FftNum> GoodThomasAlgorithmSmall<T>

pub fn new(width_fft: Arc<dyn Fft<T>>, height_fft: Arc<dyn Fft<T>>) -> Self

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

GCD(width_fft.len(), height_fft.len()) must be equal to 1

Trait Implementations

impl<T: FftNum> Direction for GoodThomasAlgorithmSmall<T>

fn fft_direction(&self) -> FftDirection

Returns FftDirection::Forward if this instance computes forward FFTs, or FftDirection::Inverse for inverse FFTs

impl<T: FftNum> Fft<T> for GoodThomasAlgorithmSmall<T>

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

Divides input and output into chunks of size self.len(), and computes a FFT on each chunk.

fn process_with_scratch( &self, buffer: &mut [Complex<T>], scratch: &mut [Complex<T>], )

Divides buffer into chunks of size self.len(), and computes a FFT on each chunk.

fn get_inplace_scratch_len(&self) -> usize

Returns the size of the scratch buffer required by process_with_scratch

fn get_outofplace_scratch_len(&self) -> usize

Returns the size of the scratch buffer required by process_outofplace_with_scratch

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

Computes a FFT in-place.

impl<T: FftNum> Length for GoodThomasAlgorithmSmall<T>

fn len(&self) -> usize

The FFT size that this algorithm can process