pub trait FFTAlgorithm<R: ?Sized + RingBase> {
// Required methods
fn len(&self) -> usize;
fn root_of_unity<S>(&self, ring: S) -> &R::Element
where S: RingStore<Type = R> + Copy;
fn unordered_fft_permutation(&self, i: usize) -> usize;
fn unordered_fft_permutation_inv(&self, i: usize) -> usize;
fn unordered_fft<V, S>(&self, values: V, ring: S)
where V: SwappableVectorViewMut<R::Element>,
S: RingStore<Type = R> + Copy;
fn unordered_inv_fft<V, S>(&self, values: V, ring: S)
where V: SwappableVectorViewMut<R::Element>,
S: RingStore<Type = R> + Copy;
// Provided methods
fn fft<V, S>(&self, values: V, ring: S)
where V: SwappableVectorViewMut<R::Element>,
S: RingStore<Type = R> + Copy { ... }
fn inv_fft<V, S>(&self, values: V, ring: S)
where V: SwappableVectorViewMut<R::Element>,
S: RingStore<Type = R> + Copy { ... }
}Expand description
Trait for objects that can perform a fast fourier transform over some ring.
Usually fast implementations of FFTs have to store a lot of precomputed data (e.g. powers of roots of unity), hence they should be represented as objects implementing this trait.
§Note on equality
If you choose to implement PartialEq for an FFTTable, and F == G, then
F and G should satisfy the following properties:
FandGsupport the same ringsF.len() == G.len()F.root_of_unity(ring) == G.root_of_unity(ring)for each supported ringringF.unordered_fft_permutation(i) == G.unordered_fft_permutation(i)for alliIn other words,FandGmust have exactly the same output forunordered_fft(and thusfft,inv_fft, …) on same inputs (w.r.t. equality given by the base rings, which are equal).
Required Methods§
Sourcefn root_of_unity<S>(&self, ring: S) -> &R::Element
fn root_of_unity<S>(&self, ring: S) -> &R::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.
Note that it is standard mathematical convention to compute the forward-transform
using the inverse of the considered root of unity. Hence, if z is the output
of FFTAlgorithm::root_of_unity(), the forward FFT FFTAlgorithm::fft()
should compute
(a_0, ..., a_(n - 1)) -> (sum_j a_j z^(-ij))_iSourcefn unordered_fft_permutation(&self, i: usize) -> usize
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().
§Example
# use feanor_math::ring::*;
# use feanor_math::rings::zn::*;
# use feanor_math::rings::zn::zn_64::*;
# use feanor_math::algorithms::*;
# use feanor_math::field::*;
# use feanor_math::algorithms::fft::*;
let ring = Zn::new(17);
let fft = cooley_tuckey::CooleyTuckeyFFT::for_zn(&ring, 3);
let (zero, one) = (ring.zero(), ring.one());
let mut values = [zero, one, one, zero, zero, zero, zero, zero];
fft.unordered_fft(&mut values, &ring);
for i in 0..8 {
let evaluation_at = ring.pow(ring.invert(fft.root_of_unity()).unwrap(), fft.unordered_fft_permutation(i));
assert_el_eq!(ring, ring.add(evaluation_at, ring.pow(evaluation_at, 2)), &values[i]);
}Sourcefn unordered_fft_permutation_inv(&self, i: usize) -> usize
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.
Sourcefn unordered_fft<V, S>(&self, values: V, ring: S)
fn unordered_fft<V, S>(&self, values: V, ring: S)
Computes the Fourier transform of the given values, but the output values are arbitrarily permuted
(in a way compatible with FFTAlgorithm::unordered_inv_fft()).
Note that the FFT of a sequence a_0, ..., a_(N - 1) is defined as Fa_k = sum_i a_i z^(-ik)
where z is an N-th root of unity.
TODO: On next breaking release, just take slice instead of VectorViews.
This might require the user to copy the data once, but so far most algorithms copy
it anyway, because this will make subsequent memory accesses more predictable and
better optimized.
Maybe also consider taking the ring by &RingBase, since this would then allow
for dynamic dispatch.
Sourcefn unordered_inv_fft<V, S>(&self, values: V, ring: S)
fn unordered_inv_fft<V, S>(&self, values: V, ring: S)
Inverse to FFTAlgorithm::unordered_fft(), with basically the same contract.
TODO: On next breaking release, just take slice instead of VectorViews.
This might require the user to copy the data once, but so far most algorithms copy
it anyway, because this will make subsequent memory accesses more predictable and
better optimized.
Maybe also consider taking the ring by &RingBase, since this would then allow
for dynamic dispatch.
Provided Methods§
Sourcefn fft<V, S>(&self, values: V, ring: S)
fn fft<V, S>(&self, values: V, ring: S)
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).
§Panics
This function panics if values.len() != self.len().
TODO: On next breaking release, just take slice instead of VectorViews.
This might require the user to copy the data once, but so far most algorithms copy
it anyway, because this will make subsequent memory accesses more predictable and
better optimized.
Maybe also consider taking the ring by &RingBase, since this would then allow
for dynamic dispatch.
Sourcefn inv_fft<V, S>(&self, values: V, ring: S)
fn inv_fft<V, S>(&self, values: V, ring: S)
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().
§Panics
This function panics if values.len() != self.len().
TODO: On next breaking release, just take slice instead of VectorViews.
This might require the user to copy the data once, but so far most algorithms copy
it anyway, because this will make subsequent memory accesses more predictable and
better optimized.
Maybe also consider taking the ring by &RingBase, since this would then allow
for dynamic dispatch.
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.