Struct rustfft::algorithm::RadersAlgorithm

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

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;
use rustfft::num_traits::Zero;

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

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

let fft = RadersAlgorithm::new(1201, inner_fft);
fft.process(&mut input, &mut output);

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.

Methods

impl<T: FFTnum> RadersAlgorithm<T>

pub fn new(len: usize, inner_fft: Arc<dyn FFT<T>>) -> Self

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

Note that this constructor is quite expensive to run; This algorithm must run a FFT of size n - 1 within the constructor. This further underlines the fact that Rader's Algorithm is more expensive to run than other FFT algorithms

Note also that if len is not prime, this algorithm may silently produce garbage output

Trait Implementations

impl<T: FFTnum> FFT<T> for RadersAlgorithm<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 chunks of length self.len(), then computes an FFT on each chunk.

impl<T> IsInverse for RadersAlgorithm<T>

fn is_inverse(&self) -> bool

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

impl<T> Length for RadersAlgorithm<T>

fn len(&self) -> usize

The FFT size that this algorithm can process