[−][src]Struct rustfft::algorithm::RadersAlgorithm
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]
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]
pub fn fft_direction(&self) -> FftDirection
[src]
impl<T: FftNum> Fft<T> for RadersAlgorithm<T>
[src]
pub fn process_outofplace_with_scratch(
&self,
input: &mut [Complex<T>],
output: &mut [Complex<T>],
scratch: &mut [Complex<T>]
)
[src]
&self,
input: &mut [Complex<T>],
output: &mut [Complex<T>],
scratch: &mut [Complex<T>]
)
pub fn process_with_scratch(
&self,
buffer: &mut [Complex<T>],
scratch: &mut [Complex<T>]
)
[src]
&self,
buffer: &mut [Complex<T>],
scratch: &mut [Complex<T>]
)
pub fn get_inplace_scratch_len(&self) -> usize
[src]
pub fn get_outofplace_scratch_len(&self) -> usize
[src]
pub fn process(&self, buffer: &mut [Complex<T>])
[src]
impl<T: FftNum> Length for RadersAlgorithm<T>
[src]
Auto Trait Implementations
impl<T> !RefUnwindSafe for RadersAlgorithm<T>
[src]
impl<T> Send for RadersAlgorithm<T> where
T: Send,
[src]
T: Send,
impl<T> Sync for RadersAlgorithm<T> where
T: Sync,
[src]
T: Sync,
impl<T> Unpin for RadersAlgorithm<T>
[src]
impl<T> !UnwindSafe for RadersAlgorithm<T>
[src]
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,