Struct GeneralCooleyTukeyFFT 

pub struct GeneralCooleyTukeyFFT<R_main, R_twiddle, H, T1, T2>
where
    R_main: ?Sized + RingBase,
    R_twiddle: ?Sized + RingBase,
    H: Homomorphism<R_twiddle, R_main>,
    T1: FFTAlgorithm<R_main>,
    T2: FFTAlgorithm<R_main>,
{ /* private fields */ }

Available on crate feature unstable-enable only.

A generic variant of the Cooley-Tukey FFT algorithm that can be used to compute the Fourier transform of an array of length n1 * n2 given Fourier transforms for length n1 resp. n2.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

Implementations

impl<R, T1, T2> GeneralCooleyTukeyFFT<R::Type, R::Type, Identity<R>, T1, T2>

where R: RingStore, T1: FFTAlgorithm<R::Type>, T2: FFTAlgorithm<R::Type>,

pub fn new_with_pows<F>( ring: R, root_of_unity_pows: F, left_table: T1, right_table: T2, ) -> Self

where F: FnMut(i64) -> El<R>,

Creates a new GeneralCooleyTukeyFFT over the given ring of length n, based on FFTs of length n1 and n2, where n = n1 * n2.

The closure root_of_unity_pows should, on input i, return z^i for the primitive n-th root of unity z satisfying z^n1 == right_table.root_of_unity() and z^n2 - left_table.root_of_unity(), where n1 and n2 are the lengths of left_table and right_table, respectively.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

pub fn new( ring: R, root_of_unity: El<R>, left_table: T1, right_table: T2, ) -> Self

Creates a new GeneralCooleyTukeyFFT over the given ring of length n, based on FFTs of length n1 and n2, where n = n1 * n2.

The given root of unity should be the primitive n-th root of unity satisfying root_of_unity^n1 == right_table.root_of_unity() and root_of_unity^n2 - left_table.root_of_unity(), where n1 and n2 are the lengths of left_table and right_table, respectively.

Do not use this for approximate rings, as computing the powers of root_of_unity will incur avoidable precision loss.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

impl<R_main, R_twiddle, H, A1, A2> GeneralCooleyTukeyFFT<R_main, R_twiddle, H, CooleyTukeyRadix3FFT<R_main, R_twiddle, H, A1>, CooleyTuckeyFFT<R_main, R_twiddle, H, A2>>

where R_main: ?Sized + RingBase, R_twiddle: ?Sized + RingBase + DivisibilityRing, H: Homomorphism<R_twiddle, R_main>, A1: Allocator + Clone, A2: Allocator + Clone,

pub fn change_ring<R_new: ?Sized + RingBase, H_new: Clone + Homomorphism<R_twiddle, R_new>>( self, new_hom: H_new, ) -> (GeneralCooleyTukeyFFT<R_new, R_twiddle, H_new, CooleyTukeyRadix3FFT<R_new, R_twiddle, H_new, A1>, CooleyTuckeyFFT<R_new, R_twiddle, H_new, A2>>, H)

Replaces the ring that this object can compute FFTs over, assuming that the current twiddle factors can be mapped into the new ring with the given homomorphism.

In particular, this function does not recompute twiddles, but uses a different homomorphism to map the current twiddles into a new ring. Hence, it is extremely cheap.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

impl<R_main, R_twiddle, H, T1, T2> GeneralCooleyTukeyFFT<R_main, R_twiddle, H, T1, T2>

where R_main: ?Sized + RingBase, R_twiddle: ?Sized + RingBase, H: Homomorphism<R_twiddle, R_main>, T1: FFTAlgorithm<R_main>, T2: FFTAlgorithm<R_main>,

pub fn new_with_pows_with_hom<F>( hom: H, root_of_unity_pows: F, left_table: T1, right_table: T2, ) -> Self

where F: FnMut(i64) -> R_twiddle::Element,

Creates a new GeneralCooleyTukeyFFT over the given ring of length n, based on FFTs of length n1 and n2, where n = n1 * n2.

The closure root_of_unity_pows should, on input i, return z^i for the primitive n-th root of unity z satisfying z^n1 == right_table.root_of_unity() and z^n2 - left_table.root_of_unity(), where n1 and n2 are the lengths of left_table and right_table, respectively.

Instead of a ring, this function takes a homomorphism R -> S. Twiddle factors that are precomputed will be stored as elements of R, while the main FFT computations will be performed in S. This allows both implicit ring conversions, and using patterns like [zn_64::ZnFastmul] to precompute some data for better performance.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

pub fn create<F>( hom: H, root_of_unity_pows: F, left_table: T1, right_table: T2, ) -> Self

where F: FnMut(i64) -> R_twiddle::Element,

Most general way to create a GeneralCooleyTukeyFFT. Currently equivalent to GeneralCooleyTukeyFFT::new_with_pows_with_hom().

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

pub fn left_fft_table(&self) -> &T1

Returns the length-n1 FFT used by this object to compute length-n FFTs.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

pub fn right_fft_table(&self) -> &T2

Returns the length-n2 FFT used by this object to compute length-n FFTs.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

pub fn hom<'a>(&'a self) -> &'a H

Returns the homomorphism used to map twiddle factors into the main ring during the computation of FFTs.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

pub fn new_with_hom( hom: H, root_of_unity: R_twiddle::Element, left_table: T1, right_table: T2, ) -> Self

Creates a new GeneralCooleyTukeyFFT over the given ring of length n, based on FFTs of length n1 and n2, where n = n1 * n2.

The given root of unity should be the primitive n-th root of unity satisfying root_of_unity^n1 == right_table.root_of_unity() and root_of_unity^n2 - left_table.root_of_unity(), where n1 and n2 are the lengths of left_table and right_table, respectively.

Instead of a ring, this function takes a homomorphism R -> S. Twiddle factors that are precomputed will be stored as elements of R, while the main FFT computations will be performed in S. This allows both implicit ring conversions, and using patterns like [zn_64::ZnFastmul] to precompute some data for better performance.

Do not use this for approximate rings, as computing the powers of root_of_unity will incur avoidable precision loss.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

pub fn ring<'a>( &'a self, ) -> &'a <H as Homomorphism<R_twiddle, R_main>>::CodomainStore

Returns the ring over which this object can compute FFTs.

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

Trait Implementations

impl<R_main, R_twiddle, H, T1, T2> FFTAlgorithm<R_main> for GeneralCooleyTukeyFFT<R_main, R_twiddle, H, T1, T2>

where R_main: ?Sized + RingBase, R_twiddle: ?Sized + RingBase, H: Homomorphism<R_twiddle, R_main>, T1: FFTAlgorithm<R_main>, T2: FFTAlgorithm<R_main>,

fn len(&self) -> usize

This FFTTable can compute the FFT of arrays of this length.

fn root_of_unity<S: RingStore<Type = R_main> + Copy>( &self, ring: S, ) -> &R_main::Element

The root of unity used for the FFT. While all primitive n-th roots of unity can be used equally for computing a Fourier transform, the concrete one used determines the order of the output values.

fn unordered_fft<V, S>(&self, values: V, ring: S)

where V: SwappableVectorViewMut<<R_main as RingBase>::Element>, S: RingStore<Type = R_main> + Copy,

Computes the Fourier transform of the given values, but the output values are arbitrarily permuted (in a way compatible with FFTAlgorithm::unordered_inv_fft()).

fn unordered_inv_fft<V, S>(&self, values: V, ring: S)

where V: SwappableVectorViewMut<<R_main as RingBase>::Element>, S: RingStore<Type = R_main> + Copy,

Inverse to FFTAlgorithm::unordered_fft(), with basically the same contract.

fn unordered_fft_permutation(&self, i: usize) -> usize

On input i, returns j such that unordered_fft(values)[i] contains the evaluation at z^(-j) of values (note the -, which is standard convention for Fourier transforms). Here z is the value returned by FFTAlgorithm::root_of_unity().

fn unordered_fft_permutation_inv(&self, i: usize) -> usize

The inverse of FFTAlgorithm::unordered_fft_permutation(), i.e. for all i, have self.unordered_fft_permutation_inv(self.unordered_fft_permutation(i)) == i.

fn fft<V, S>(&self, values: V, ring: S)

where V: SwappableVectorViewMut<R::Element>, S: RingStore<Type = R> + Copy,

Computes the Fourier transform of the given values over the specified ring. The output is in standard order, i.e. the i-th output element is the evaluation of the input at self.root_of_unity()^(-i) (note the -, which is standard convention for Fourier transforms).

fn inv_fft<V, S>(&self, values: V, ring: S)

where V: SwappableVectorViewMut<R::Element>, S: RingStore<Type = R> + Copy,

Computes the Fourier transform of the given values over the specified ring. The output is in standard order, i.e. the i-th output element is the evaluation of the input at self.root_of_unity()^i, divided by self.len().

impl<H, T1, T2> FFTErrorEstimate for GeneralCooleyTukeyFFT<Complex64Base, Complex64Base, H, T1, T2>

where H: Homomorphism<Complex64Base, Complex64Base>, T1: FFTAlgorithm<Complex64Base> + FFTErrorEstimate, T2: FFTAlgorithm<Complex64Base> + FFTErrorEstimate,

fn expected_absolute_error(&self, input_bound: f64, input_error: f64) -> f64

Available on crate feature unstable-enable only.

This is only true if the table is created with the crate::rings::float_complex::Complex64-specific creator functions. Note that this is a worst-case estimate and likely to significantly overestimate the error.

impl<R_main, R_twiddle, H, T1, T2> PartialEq for GeneralCooleyTukeyFFT<R_main, R_twiddle, H, T1, T2>

where R_main: ?Sized + RingBase, R_twiddle: ?Sized + RingBase, H: Homomorphism<R_twiddle, R_main>, T1: FFTAlgorithm<R_main> + PartialEq, T2: FFTAlgorithm<R_main> + PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.