Trait winter_math::fft::fft_inputs::FftInputs

source ·

pub trait FftInputs<E: FieldElement> {
    // Required methods
    fn len(&self) -> usize;
    fn butterfly(&mut self, offset: usize, stride: usize);
    fn butterfly_twiddle(
        &mut self,
        twiddle: E::BaseField,
        offset: usize,
        stride: usize
    );
    fn swap(&mut self, i: usize, j: usize);
    fn shift_by_series(&mut self, offset: E::BaseField, increment: E::BaseField);
    fn shift_by(&mut self, offset: E::BaseField);

    // Provided methods
    fn permute(&mut self) { ... }
    fn fft_in_place(&mut self, twiddles: &[E::BaseField]) { ... }
    fn fft_in_place_raw(
        &mut self,
        twiddles: &[E::BaseField],
        count: usize,
        stride: usize,
        offset: usize
    ) { ... }
}

Expand description

Defines the interface that must be implemented by the input to fft_in_place method.

Required Methods§

source

fn len(&self) -> usize

Returns the number of elements in this input.

source

fn butterfly(&mut self, offset: usize, stride: usize)

Combines the result of smaller number theoretic transform into a larger NTT.

source

fn butterfly_twiddle( &mut self, twiddle: E::BaseField, offset: usize, stride: usize )

Combines the result of smaller number theoretic transform multiplied with a twiddle factor into a larger NTT.

source

fn swap(&mut self, i: usize, j: usize)

Swaps the element at index i with the element at index j. Specifically:

elem_i <-> elem_j

§Panics

Panics if i or j are out of bounds.

source

fn shift_by_series(&mut self, offset: E::BaseField, increment: E::BaseField)

Multiplies every element in this input by a series of increment. Specifically:

elem_i = elem_i * offset * increment^i

source

fn shift_by(&mut self, offset: E::BaseField)

Multiplies every element in this input by offset. Specifically:

elem_i = elem_i * offset

Provided Methods§

source

fn permute(&mut self)

Permutes the elements in this input using the permutation defined by the given permutation index.

The permutation index is a number between 0 and self.len() - 1 that specifies the permutation to apply to the input. The permutation is applied in place, so the input is replaced with the result of the permutation. The permutation is applied by swapping elements in the input.

§Panics

Panics if the permutation index is out of bounds.

source

fn fft_in_place(&mut self, twiddles: &[E::BaseField])

Applies the FFT to this input.

The FFT is applied in place, so the input is replaced with the result of the FFT. The twiddles parameter specifies the twiddle factors to use for the FFT.

This is a convenience method equivalent to calling fft_in_place_raw(twiddles, 1, 1, 0).

§Panics

Panics if length of the twiddles parameter is not self.len() / 2.

source

fn fft_in_place_raw( &mut self, twiddles: &[E::BaseField], count: usize, stride: usize, offset: usize )

Applies the FFT to this input.

The FFT is applied in place, so the input is replaced with the result of the FFT. The twiddles parameter specifies the twiddle factors to use for the FFT.