Trait miden_processor::math::fft::fft_inputs::FftInputs

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

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

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

Required Methods

fn len(&self) -> usize

Returns the number of elements in this input.

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

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

fn butterfly_twiddle( &mut self, twiddle: <E as FieldElement>::BaseField, offset: usize, stride: usize )

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

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.

fn shift_by_series( &mut self, offset: <E as FieldElement>::BaseField, increment: <E as FieldElement>::BaseField )

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

elem_i = elem_i * offset * increment^i

fn shift_by(&mut self, offset: <E as FieldElement>::BaseField)

Multiplies every element in this input by offset. Specifically:

elem_i = elem_i * offset

Provided Methods

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.

fn fft_in_place(&mut self, twiddles: &[<E as FieldElement>::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.

fn fft_in_place_raw( &mut self, twiddles: &[<E as FieldElement>::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.

Panics

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

Implementations on Foreign Types

impl<E> FftInputs<E> for [E]where E: FieldElement,

Implements FftInputs for a slice of field elements.

fn len(&self) -> usize

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

fn butterfly_twiddle( &mut self, twiddle: <E as FieldElement>::BaseField, offset: usize, stride: usize )

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

fn shift_by_series( &mut self, offset: <E as FieldElement>::BaseField, increment: <E as FieldElement>::BaseField )

fn shift_by(&mut self, offset: <E as FieldElement>::BaseField)

impl<E, const N: usize> FftInputs<E> for [[E; N]]where E: FieldElement,

Implements FftInputs for a slice of field element arrays.

fn len(&self) -> usize

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

fn butterfly_twiddle( &mut self, twiddle: <E as FieldElement>::BaseField, offset: usize, stride: usize )

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

fn shift_by(&mut self, offset: <E as FieldElement>::BaseField)

fn shift_by_series( &mut self, offset: <E as FieldElement>::BaseField, increment: <E as FieldElement>::BaseField )

Implementors