Struct rustfft::algorithm::RadersAlgorithm [−][src]
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; 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>
[src]
impl<T: FftNum> RadersAlgorithm<T>
[src]pub fn new(inner_fft: Arc<dyn Fft<T>>) -> Self
[src]
pub fn new(inner_fft: Arc<dyn Fft<T>>) -> Self
[src]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>
[src]
impl<T: FftNum> Direction for RadersAlgorithm<T>
[src]fn fft_direction(&self) -> FftDirection
[src]
fn fft_direction(&self) -> FftDirection
[src]Returns FftDirection::Forward if this instance computes forward FFTs, or FftDirection::Inverse for inverse FFTs
impl<T: FftNum> Fft<T> for RadersAlgorithm<T>
[src]
impl<T: FftNum> Fft<T> for RadersAlgorithm<T>
[src]fn process_outofplace_with_scratch(
&self,
input: &mut [Complex<T>],
output: &mut [Complex<T>],
scratch: &mut [Complex<T>]
)
[src]
fn process_outofplace_with_scratch(
&self,
input: &mut [Complex<T>],
output: &mut [Complex<T>],
scratch: &mut [Complex<T>]
)
[src]Divides input
and output
into chunks of size self.len()
, and computes a FFT on each chunk. Read more
fn process_with_scratch(
&self,
buffer: &mut [Complex<T>],
scratch: &mut [Complex<T>]
)
[src]
fn process_with_scratch(
&self,
buffer: &mut [Complex<T>],
scratch: &mut [Complex<T>]
)
[src]Divides buffer
into chunks of size self.len()
, and computes a FFT on each chunk. Read more
fn get_inplace_scratch_len(&self) -> usize
[src]
fn get_inplace_scratch_len(&self) -> usize
[src]Returns the size of the scratch buffer required by process_with_scratch
Read more
fn get_outofplace_scratch_len(&self) -> usize
[src]
fn get_outofplace_scratch_len(&self) -> usize
[src]Returns the size of the scratch buffer required by process_outofplace_with_scratch
Read more
Auto Trait Implementations
impl<T> !RefUnwindSafe for RadersAlgorithm<T>
impl<T> Send for RadersAlgorithm<T> where
T: Send,
T: Send,
impl<T> Sync for RadersAlgorithm<T> where
T: Sync,
T: Sync,