Module convolution

Modules

fft

Contains an implementation of computing convolutions using complex FFTs.

generic_tests

karatsuba

Contains an optimized implementation of Karatsuba’s for computing convolutions

ntt

rns

Structs

KaratsubaAlgorithm

Implementation of convolutions that uses Karatsuba’s algorithm with a threshold defined by KaratsubaHint.

Constants

STANDARD_CONVOLUTION

Good default algorithm for computing convolutions, using Karatsuba’s algorithm with a threshold defined by KaratsubaHint.

Traits

ConvolutionAlgorithm

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

KaratsubaHint

Trait to allow rings to customize the parameters with which KaratsubaAlgorithm will compute convolutions over the ring.

PreparedConvolutionAlgorithm

Trait for convolution algorithms that can “prepare” one (or both) operands in advance by computing additional data, and then use this data to perform the actual convolution more efficiently.

PreparedConvolutionOperation

Operation that only makes sense when C implements PreparedConvolutionAlgorithm. Used together with ConvolutionAlgorithm::specialize_prepared_convolution() as a workaround for specialization.