Struct RadersAvx2 

pub struct RadersAvx2<A: AvxNum, T> {
    input_index_multiplier: VectorizedMultiplyMod,
    input_index_init: __m256i,
    output_index_mapping: Box<[__m128i]>,
    twiddles: Box<[A::VectorType]>,
    inner_fft: Arc<dyn Fft<T>>,
    len: usize,
    inplace_scratch_len: usize,
    outofplace_scratch_len: usize,
    immut_scratch_len: usize,
    direction: FftDirection,
    _phantom: PhantomData<T>,
}

Implementation of Rader’s Algorithm, using AVX2 instructions.

This algorithm computes a prime-sized FFT in O(nlogn) time. It does this by converting this size n FFT into a size (n - 1) which is guaranteed to be composite.

The worst case for this algorithm is when (n - 1) is 2 * prime, resulting in a Cunningham Chain

Rader’s Algorithm is relatively expensive compared to other FFT algorithms. Benchmarking shows that it is up to an order of magnitude slower than similar composite sizes.

Fields

input_index_multiplier: VectorizedMultiplyMod

input_index_init: __m256i

output_index_mapping: Box<[__m128i]>

twiddles: Box<[A::VectorType]>

inner_fft: Arc<dyn Fft<T>>

len: usize

inplace_scratch_len: usize

outofplace_scratch_len: usize

immut_scratch_len: usize

direction: FftDirection

_phantom: PhantomData<T>

Implementations

impl<A: AvxNum, T: FftNum> RadersAvx2<A, T>

pub fn new(inner_fft: Arc<dyn Fft<T>>) -> Result<Self, ()>

Preallocates necessary arrays and precomputes necessary data to efficiently compute the FFT Returns Ok(instance) if this machine has the required instruction sets (“avx”, “fma”, and “avx2”), Err() if some instruction sets are missing

Panics

Panics if inner_fft_len() + 1 is not a prime number.

unsafe fn new_with_avx(inner_fft: Arc<dyn Fft<T>>) -> Self

unsafe fn prepare_raders(&self, input: &[Complex<A>], output: &mut [Complex<A>])

unsafe fn finalize_raders( &self, input: &[Complex<A>], output: &mut [Complex<A>], )

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

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

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

Trait Implementations

impl<A: AvxNum, T> Direction for RadersAvx2<A, T>

fn fft_direction(&self) -> FftDirection

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

impl<A: AvxNum, T: FftNum> Fft<T> for RadersAvx2<A, T>

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

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

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 get_immutable_scratch_len(&self) -> usize

Returns the size of the scratch buffer required by process_immutable_with_scratch

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

Computes a FFT in-place.

impl<A: AvxNum, T> Length for RadersAvx2<A, T>

fn len(&self) -> usize

The FFT size that this algorithm can process