feanor_math::algorithms::convolution

Trait ConvolutionAlgorithm

Source 
pub trait ConvolutionAlgorithm<R: ?Sized + RingBase> {
    // Required methods
    fn compute_convolution<S: RingStore<Type = R> + Copy, V1: VectorView<R::Element>, V2: VectorView<R::Element>>(
        &self,
        lhs: V1,
        rhs: V2,
        dst: &mut [R::Element],
        ring: S,
    );
    fn supports_ring<S: RingStore<Type = R> + Copy>(&self, ring: S) -> bool;
}
Expand description

Trait for objects that can compute a convolution over some ring.

§Example

struct NaiveConvolution;
// we support all rings!
impl<R: ?Sized + RingBase> ConvolutionAlgorithm<R> for NaiveConvolution {
    fn compute_convolution<S: RingStore<Type = R>, V1: VectorView<R::Element>, V2: VectorView<R::Element>>(&self, lhs: V1, rhs: V2, dst: &mut [R::Element], ring: S) {
        for i in 0..(lhs.len() + rhs.len() - 1) {
            for j in max(0, i as isize - rhs.len() as isize + 1)..min(lhs.len() as isize, i as isize + 1) {
                ring.add_assign(&mut dst[i], ring.mul_ref(lhs.at(j as usize), rhs.at(i - j as usize)));
            }
        }
    }
    fn supports_ring<S: RingStore<Type = R>>(&self, _: S) -> bool
        where S: Copy
    { true }
}
let lhs = [1, 2, 3, 4, 5];
let rhs = [2, 3, 4, 5, 6];
let mut expected = [0; 10];
let mut actual = [0; 10];
STANDARD_CONVOLUTION.compute_convolution(lhs, rhs, &mut expected, StaticRing::<i64>::RING);
NaiveConvolution.compute_convolution(lhs, rhs, &mut actual, StaticRing::<i64>::RING);
assert_eq!(expected, actual);

Required Methods§

Source

fn compute_convolution<S: RingStore<Type = R> + Copy, V1: VectorView<R::Element>, V2: VectorView<R::Element>>( &self, lhs: V1, rhs: V2, dst: &mut [R::Element], ring: S, )

Elementwise adds the convolution of lhs and rhs to dst.

In other words, computes dst[i] += sum_j lhs[j] * rhs[i - j] for all i, where j runs through all positive integers for which lhs[j] and rhs[i - j] are defined, i.e. not out-of-bounds.

In particular, it is necessary that dst.len() >= lhs.len() + rhs.len() - 1. However, to allow for more efficient implementations, it is instead required that dst.len() >= lhs.len() + rhs.len().

§Panic

Panics if dst is shorter than lhs.len() + rhs.len() - 1. May panic if dst is shorter than lhs.len() + rhs.len().

Source

fn supports_ring<S: RingStore<Type = R> + Copy>(&self, ring: S) -> bool

Returns whether this convolution algorithm supports computations of the given ring.

Note that most algorithms will support all rings of type R. However in some cases, e.g. for finite fields, required data might only be precomputed for some moduli, and thus only these will be supported.

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.

Implementors§