Crate p3_dft

This crate contains some DFT implementations.

Structs

DifButterfly

DIF (Decimation-In-Frequency) butterfly operation.

DifButterflyZeros

DIF (Decimation-In-Frequency) butterfly operation where x_2 is guaranteed to be zero.

DitButterfly

DIT (Decimation-In-Time) butterfly operation.

NaiveDft

Radix2Bowers

The Bowers G FFT algorithm. See: “Improved Twiddle Access for Fast Fourier Transforms”

Radix2DFTSmallBatch

An FFT algorithm which divides a butterfly network’s layers into two halves.

Radix2Dit

Radix-2 Decimation-in-Time FFT over a two-adic subgroup.

Radix2DitParallel

A parallel FFT algorithm which divides a butterfly network’s layers into two halves.

TwiddleFreeButterfly

Butterfly with no twiddle factor (twiddle = 1).

Traits

Butterfly

A butterfly operation used in NTT to combine two values into a new pair.

TwoAdicSubgroupDft

This trait gives an interface for computing discrete fourier transforms (DFT’s) and their inverses over cosets of two-adic subgroups of a field F. It also contains combined methods which allow you to take the evaluation vector of a polynomial on a coset gH and extend it to a coset g'K for some possibly larger subgroup K and different shift g'.

Functions

divide_by_height

Divide each coefficient of the given matrix by its height.