Struct NeighborsLastMultiThread

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

A multi-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.

log_num_shares: usize

The base-2 logarithm of number of equal-sized shares that the problem should be split into. Each share needs to do the same amount of work. If you have equally powered cores available, this should be the base-2 logarithm of the number of cores.

Implementations

impl<DC> NeighborsLastMultiThread<DC>

pub fn new(domain_context: DC, log_num_shares: usize) -> Self

Convenience constructor which sets log_base_len to a reasonable default.

Trait Implementations

impl<DC: DomainContext + Sync> AdditiveNTT for NeighborsLastMultiThread<DC>

type Field = <DC as DomainContext>::Field

fn forward_transform<P: PackedField<Scalar = Self::Field>>( &self, data_orig: 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 NeighborsLastMultiThread<DC>

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

Formats the value using the given formatter.