Struct RadersAlgorithm

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

Implementation of Rader’s Algorithm

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) FFT, which is guaranteed to be composite.

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

// Computes a forward FFT of size 1201 (prime number), using Rader's Algorithm
use rustfft::algorithm::RadersAlgorithm;
use rustfft::{Fft, FftPlanner};
use rustfft::num_complex::Complex;

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

// plan a FFT of size n - 1 = 1200
let mut planner = FftPlanner::new();
let inner_fft = planner.plan_fft_forward(1200);

let fft = RadersAlgorithm::new(inner_fft);
fft.process(&mut buffer);

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. In the example size above of 1201, benchmarking shows that it takes 2.5x more time to compute than a FFT of size 1200.

Implementations

impl<T: FftNum> RadersAlgorithm<T>

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

Creates a FFT instance which will process inputs/outputs of size inner_fft.len() + 1.

Note that this constructor is quite expensive to run; This algorithm must compute a FFT using inner_fft within the constructor. This further underlines the fact that Rader’s Algorithm is more expensive to run than other FFT algorithms

Panics

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

Trait Implementations

impl<T: FftNum> Direction for RadersAlgorithm<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 RadersAlgorithm<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 RadersAlgorithm<T>

fn len(&self) -> usize

The FFT size that this algorithm can process