Struct NeighborsLastSingleThread

pub struct NeighborsLastSingleThread<DC> {
    pub domain_context: DC,
    pub log_base_len: usize,
}

A single-threaded implementation of AdditiveNTT.

The code only makes sure that it’s fast for a large data input. For small inputs, it can be comparatively slow!

The implementation is depth-first, but calls a breadth-first implementation as a base case.

Note that “neighbors last” refers to the memory layout for the NTT: In the last layer of this NTT algorithm, neighboring elements speak to each other. In the classic FFT that’s usually the case for “decimation in frequency”.

Fields

domain_context: DC

The domain context from which the twiddles are pulled.

log_base_len: usize

Determines when to switch from depth-first to the breadth-first base case.

Implementations

impl<DC> NeighborsLastSingleThread<DC>

pub fn new(domain_context: DC) -> Self

Convenience constructor which sets log_base_len to a reasonable default.

Trait Implementations

impl<DC: DomainContext> AdditiveNTT for NeighborsLastSingleThread<DC>

type Field = <DC as DomainContext>::Field

fn forward_transform<P: PackedField<Scalar = Self::Field>>( &self, data: FieldSliceMut<'_, P>, skip_early: usize, skip_late: usize, )

Forward transformation as defined in DP24, Section 2.3.

fn inverse_transform<P: PackedField<Scalar = Self::Field>>( &self, _data_orig: FieldSliceMut<'_, P>, _skip_early: usize, _skip_late: usize, )

Inverse transformation of Self::forward_transform.

fn domain_context(&self) -> &impl DomainContext<Field = DC::Field>

The associated DomainContext.

fn log_domain_size(&self) -> usize

See DomainContext::log_domain_size.

fn subspace(&self, i: usize) -> BinarySubspace<Self::Field>

See DomainContext::subspace.

fn twiddle(&self, i: usize, j: usize) -> Self::Field

See DomainContext::twiddle.

impl<DC: Debug> Debug for NeighborsLastSingleThread<DC>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.