Aleph::NTT< MOD, ROOT >::Plan Class Reference

Precomputed plans for NTT transforms. More...

#include <ntt.H>

Collaboration diagram for Aleph::NTT< MOD, ROOT >::Plan:

Public Member Functions
	Plan (const size_t n)
	Construct a reusable plan for a fixed transform size.
size_t	size () const noexcept
	Return the transform size bound to the plan.
void	transform (Array< uint64_t > &a, const bool invert) const
	In-place forward or inverse transform.
Array< uint64_t >	transformed (const Array< uint64_t > &input, const bool invert=false) const
	Transform an input array and return the result.
Array< uint64_t >	multiply (const Array< uint64_t > &a, const Array< uint64_t > &b) const
	Multiply two polynomials using this plan size.
void	ptransform (ThreadPool &pool, Array< uint64_t > &a, const bool invert, const size_t chunk_size=0) const
	Parallel in-place transform using a ThreadPool.
Array< uint64_t >	ptransformed (ThreadPool &pool, const Array< uint64_t > &input, const bool invert=false, const size_t chunk_size=0) const
	Parallel transform returning a new array.
Array< uint64_t >	pmultiply (ThreadPool &pool, const Array< uint64_t > &a, const Array< uint64_t > &b, const size_t chunk_size=0) const
	Parallel polynomial multiplication using this plan size.
void	transform_batch (Array< Array< uint64_t > > &batch, const bool invert) const
	Sequential batch transform for equal-sized inputs.
void	ptransform_batch (ThreadPool &pool, Array< Array< uint64_t > > &batch, const bool invert, const size_t chunk_size=0) const
	Parallel batch transform for equal-sized inputs.
Array< Array< uint64_t > >	transformed_batch (const Array< Array< uint64_t > > &input, const bool invert=false) const
	Return a transformed copy of an entire batch.
Array< Array< uint64_t > >	ptransformed_batch (ThreadPool &pool, const Array< Array< uint64_t > > &input, const bool invert=false, const size_t chunk_size=0) const
	Return a parallel-transformed copy of an entire batch.

Private Types
enum class	Strategy { power_of_two , bluestein }

Private Member Functions
void	apply_scalar_butterfly_range (Array< uint64_t > &a, const Array< uint64_t > &twiddles, const size_t base, const size_t half, const size_t offset, const size_t begin, const size_t end) const
bool	should_use_avx2 (ThreadPool *const pool) const noexcept
bool	should_use_neon (ThreadPool *const pool) const noexcept
void	initialize_bit_reversal ()
void	initialize_twiddles ()
void	initialize_power_of_two_plan ()
void	initialize_bluestein_plan ()
void	apply_bit_reversal (Array< uint64_t > &a) const noexcept
void	lift_input (Array< uint64_t > &a, ThreadPool *const pool, const size_t chunk_size) const
void	scale_inverse (Array< uint64_t > &a, ThreadPool *const pool, const size_t chunk_size) const
void	lower_output (Array< uint64_t > &a, ThreadPool *const pool, const size_t chunk_size) const
void	apply_butterflies_scalar (Array< uint64_t > &a, const Array< uint64_t > &twiddles, ThreadPool *const pool, const size_t chunk_size) const
void	apply_butterflies (Array< uint64_t > &a, const bool invert, ThreadPool *const pool, const size_t chunk_size) const
void	apply_bluestein_transform (Array< uint64_t > &a, const bool invert, ThreadPool *const pool, const size_t chunk_size) const
void	apply_transform (Array< uint64_t > &a, const bool invert, const Representation input_repr, const Representation output_repr, ThreadPool *const pool, const size_t chunk_size) const
Array< uint64_t >	multiply_impl (const Array< uint64_t > &a, const Array< uint64_t > &b, ThreadPool *const pool, const size_t chunk_size) const

Static Private Member Functions
template<typename F >
static void	for_each_index (ThreadPool *const pool, const size_t count, F &&fn, const size_t chunk_size)

Private Attributes
Strategy	strategy_ = Strategy::power_of_two
size_t	n_ = 0
size_t	log_n_ = 0
Array< size_t >	bit_rev_
Array< uint64_t >	twiddles_fwd_
Array< uint64_t >	twiddles_inv_
uint64_t	inv_n_ = 0
uint64_t	inv_n_std_ = 1
size_t	bluestein_size_ = 0
Array< uint64_t >	bluestein_chirp_fwd_
Array< uint64_t >	bluestein_chirp_inv_
Array< uint64_t >	bluestein_kernel_forward_
Array< uint64_t >	bluestein_kernel_inverse_
std::shared_ptr< const Plan >	bluestein_plan_

Detailed Description

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>
class Aleph::NTT< MOD, ROOT >::Plan

Precomputed plans for NTT transforms.

Stores twiddle factors and auxiliary data (like bit-reversal tables or Bluestein kernels) for a fixed transform size.

Definition at line 465 of file ntt.H.

Member Enumeration Documentation

Strategy

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

enum class Aleph::NTT::Plan::Strategy

strongprivate

Enumerator
power_of_two
bluestein

Definition at line 467 of file ntt.H.

Constructor & Destructor Documentation

Plan()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Aleph::NTT< MOD, ROOT >::Plan::Plan ( const size_t  n )

inlineexplicit

Construct a reusable plan for a fixed transform size.

Parameters

n	Transform size. It must be a power of two supported by MOD - 1.

Exceptions

std::invalid_argument

if n is zero, not a power of two, or exceeds the modulus capability.

Definition at line 1085 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan(), Aleph::NTT< MOD, ROOT >::Plan::initialize_power_of_two_plan(), Aleph::NTT< MOD, ROOT >::Plan::inv_n_std_, MOD, Aleph::mod_inv(), Aleph::NTT< MOD, ROOT >::Plan::n_, Aleph::NTT< MOD, ROOT >::supports_power_of_two_size(), and Aleph::NTT< MOD, ROOT >::validate_supported_size().

Member Function Documentation

apply_bit_reversal()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::apply_bit_reversal ( Array< uint64_t > &  a ) const

inlineprivatenoexcept

Definition at line 815 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::bit_rev_, and Aleph::NTT< MOD, ROOT >::Plan::n_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_transform().

apply_bluestein_transform()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform ( Array< uint64_t > &  a, const bool  invert, ThreadPool *const  pool, const size_t  chunk_size  ) const

inlineprivate

Definition at line 912 of file ntt.H.

References ah_runtime_error_unless, Aleph::and, Aleph::NTT< MOD, ROOT >::Plan::bluestein_chirp_fwd_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_chirp_inv_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_kernel_forward_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_kernel_inverse_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_plan_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_size_, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::for_each_index(), Aleph::NTT< MOD, ROOT >::Plan::inv_n_std_, MOD, Aleph::mod_mul(), Aleph::NTT< MOD, ROOT >::Plan::n_, Aleph::ThreadPool::num_threads(), and Aleph::Array< T >::size().

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_transform().

apply_butterflies()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies ( Array< uint64_t > &  a, const bool  invert, ThreadPool *const  pool, const size_t  chunk_size  ) const

inlineprivate

Definition at line 884 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies_scalar(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::should_use_avx2(), Aleph::NTT< MOD, ROOT >::Plan::should_use_neon(), Aleph::NTT< MOD, ROOT >::Plan::twiddles_fwd_, and Aleph::NTT< MOD, ROOT >::Plan::twiddles_inv_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_transform().

apply_butterflies_scalar()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies_scalar ( Array< uint64_t > &  a, const Array< uint64_t > &  twiddles, ThreadPool *const  pool, const size_t  chunk_size  ) const

inlineprivate

Definition at line 859 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::apply_scalar_butterfly_range(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::for_each_index(), Aleph::NTT< MOD, ROOT >::Plan::log_n_, Aleph::NTT< MOD, ROOT >::Plan::n_, and offset.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies().

apply_scalar_butterfly_range()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::apply_scalar_butterfly_range ( Array< uint64_t > &  a, const Array< uint64_t > &  twiddles, const size_t  base, const size_t  half, const size_t  offset, const size_t  begin, const size_t  end  ) const

inlineprivate

Definition at line 510 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::add_mod(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::mctx_, offset, and Aleph::NTT< MOD, ROOT >::sub_mod().

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies_scalar().

apply_transform()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::apply_transform ( Array< uint64_t > &  a, const bool  invert, const Representation  input_repr, const Representation  output_repr, ThreadPool *const  pool, const size_t  chunk_size  ) const

inlineprivate

Definition at line 965 of file ntt.H.

References ah_invalid_argument_if, Aleph::NTT< MOD, ROOT >::Plan::apply_bit_reversal(), Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies(), Aleph::NTT< MOD, ROOT >::Plan::bluestein, Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::lift_input(), Aleph::NTT< MOD, ROOT >::Plan::lower_output(), Aleph::NTT< MOD, ROOT >::Plan::n_, Aleph::NTT< MOD, ROOT >::Plan::power_of_two, Aleph::NTT< MOD, ROOT >::Plan::scale_inverse(), Aleph::Array< T >::size(), Aleph::NTT< MOD, ROOT >::standard, and Aleph::NTT< MOD, ROOT >::Plan::strategy_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::multiply_impl(), Aleph::NTT< MOD, ROOT >::Plan::ptransform(), Aleph::NTT< MOD, ROOT >::Plan::ptransform_batch(), Aleph::NTT< MOD, ROOT >::Plan::transform(), and Aleph::NTT< MOD, ROOT >::Plan::transform_batch().

for_each_index()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

template<typename F >

static void Aleph::NTT< MOD, ROOT >::Plan::for_each_index ( ThreadPool *const  pool, const size_t  count, F &&  fn, const size_t  chunk_size  )

inlinestaticprivate

Definition at line 490 of file ntt.H.

References Aleph::and, Aleph::count(), Aleph::divide_and_conquer_partition_dp(), Aleph::ThreadPool::num_threads(), and Aleph::parallel_for_index().

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies_scalar(), Aleph::NTT< MOD, ROOT >::Plan::lift_input(), Aleph::NTT< MOD, ROOT >::Plan::lower_output(), Aleph::NTT< MOD, ROOT >::Plan::multiply_impl(), and Aleph::NTT< MOD, ROOT >::Plan::scale_inverse().

initialize_bit_reversal()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::initialize_bit_reversal ( )

inlineprivate

Definition at line 696 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::bit_rev_, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), and Aleph::NTT< MOD, ROOT >::Plan::n_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::initialize_power_of_two_plan().

initialize_bluestein_plan()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan ( )

inlineprivate

Definition at line 758 of file ntt.H.

References ah_invalid_argument_if, Aleph::NTT< MOD, ROOT >::Plan::bluestein, Aleph::NTT< MOD, ROOT >::Plan::bluestein_chirp_fwd_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_chirp_inv_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_kernel_forward_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_kernel_inverse_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_plan_, Aleph::NTT< MOD, ROOT >::Plan::bluestein_size_, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), MOD, Aleph::mod_exp(), Aleph::mod_inv(), Aleph::NTT< MOD, ROOT >::Plan::n_, Aleph::NTT< MOD, ROOT >::next_power_of_two(), Aleph::NTT< MOD, ROOT >::primitive_root_of_order(), Aleph::NTT< MOD, ROOT >::Plan::strategy_, Aleph::NTT< MOD, ROOT >::supports_power_of_two_size(), and Aleph::NTT< MOD, ROOT >::validate_root_order().

Referenced by Aleph::NTT< MOD, ROOT >::Plan::Plan().

initialize_power_of_two_plan()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::initialize_power_of_two_plan ( )

inlineprivate

Definition at line 745 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::initialize_bit_reversal(), Aleph::NTT< MOD, ROOT >::Plan::initialize_twiddles(), Aleph::NTT< MOD, ROOT >::Plan::inv_n_, Aleph::NTT< MOD, ROOT >::Plan::log_n_, Aleph::NTT< MOD, ROOT >::mctx_, MOD, Aleph::mod_inv(), Aleph::NTT< MOD, ROOT >::Plan::n_, Aleph::NTT< MOD, ROOT >::Plan::power_of_two, and Aleph::NTT< MOD, ROOT >::Plan::strategy_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::Plan().

initialize_twiddles()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::initialize_twiddles ( )

inlineprivate

Definition at line 711 of file ntt.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::log_n_, Aleph::NTT< MOD, ROOT >::mctx_, MOD, Aleph::mod_inv(), Aleph::NTT< MOD, ROOT >::Plan::n_, offset, Aleph::NTT< MOD, ROOT >::primitive_root_of_unity(), Aleph::NTT< MOD, ROOT >::Plan::twiddles_fwd_, and Aleph::NTT< MOD, ROOT >::Plan::twiddles_inv_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::initialize_power_of_two_plan().

lift_input()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::lift_input ( Array< uint64_t > &  a, ThreadPool *const  pool, const size_t  chunk_size  ) const

inlineprivate

Definition at line 823 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::for_each_index(), Aleph::NTT< MOD, ROOT >::mctx_, MOD, and Aleph::NTT< MOD, ROOT >::Plan::n_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_transform().

lower_output()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::lower_output ( Array< uint64_t > &  a, ThreadPool *const  pool, const size_t  chunk_size  ) const

inlineprivate

Definition at line 847 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::for_each_index(), Aleph::NTT< MOD, ROOT >::mctx_, and Aleph::NTT< MOD, ROOT >::Plan::n_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_transform().

multiply()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array< uint64_t > Aleph::NTT< MOD, ROOT >::Plan::multiply ( const Array< uint64_t > &  a, const Array< uint64_t > &  b  ) const

inline

Multiply two polynomials using this plan size.

Parameters

a	First polynomial.
b	Second polynomial.

Returns

Convolution modulo MOD.

Exceptions

std::invalid_argument

if the result length exceeds the plan size.

Definition at line 1141 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::multiply_impl().

Referenced by Aleph::NTT< MOD, ROOT >::multiply().

multiply_impl()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array< uint64_t > Aleph::NTT< MOD, ROOT >::Plan::multiply_impl ( const Array< uint64_t > &  a, const Array< uint64_t > &  b, ThreadPool *const  pool, const size_t  chunk_size  ) const

inlineprivate

Definition at line 1008 of file ntt.H.

References ah_invalid_argument_if, Aleph::NTT< MOD, ROOT >::Plan::apply_transform(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::for_each_index(), Aleph::Array< T >::is_empty(), Aleph::NTT< MOD, ROOT >::mctx_, MOD, Aleph::mod_mul(), Aleph::NTT< MOD, ROOT >::montgomery, Aleph::NTT< MOD, ROOT >::Plan::n_, Aleph::NTT< MOD, ROOT >::padded_copy(), Aleph::NTT< MOD, ROOT >::Plan::power_of_two, Aleph::NTT< MOD, ROOT >::prefix_copy(), Aleph::Array< T >::size(), Aleph::NTT< MOD, ROOT >::standard, and Aleph::NTT< MOD, ROOT >::Plan::strategy_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::multiply(), and Aleph::NTT< MOD, ROOT >::Plan::pmultiply().

pmultiply()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array< uint64_t > Aleph::NTT< MOD, ROOT >::Plan::pmultiply ( ThreadPool &  pool, const Array< uint64_t > &  a, const Array< uint64_t > &  b, const size_t  chunk_size = 0  ) const

inline

Parallel polynomial multiplication using this plan size.

Parameters

pool	Thread pool used for transform stages and pointwise products.
a	First polynomial.
b	Second polynomial.
chunk_size	Iterations per scheduled chunk (0 selects an automatic value).

Returns

Convolution modulo MOD.

Definition at line 1198 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::multiply_impl().

Referenced by Aleph::NTT< MOD, ROOT >::pmultiply().

ptransform()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::ptransform ( ThreadPool &  pool, Array< uint64_t > &  a, const bool  invert, const size_t  chunk_size = 0  ) const

inline

Parallel in-place transform using a ThreadPool.

Parameters

pool	Thread pool used for stage-level parallelism.
a	Input/output array. Its size must equal the plan size.
invert	If true, computes the inverse NTT.
chunk_size	Iterations per scheduled chunk (0 selects an automatic value).

Definition at line 1156 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::apply_transform(), Aleph::divide_and_conquer_partition_dp(), and Aleph::NTT< MOD, ROOT >::standard.

Referenced by Aleph::NTT< MOD, ROOT >::ptransform(), and Aleph::NTT< MOD, ROOT >::Plan::ptransformed().

ptransform_batch()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::ptransform_batch ( ThreadPool &  pool, Array< Array< uint64_t > > &  batch, const bool  invert, const size_t  chunk_size = 0  ) const

inline

Parallel batch transform for equal-sized inputs.

Parallelism is applied across batch items when possible. For a single item, the internal transform itself uses the supplied thread pool.

Parameters

pool	Thread pool used for execution.
batch	Batch of arrays; every item must match the plan size.
invert	If true, computes inverse transforms.
chunk_size	Iterations per scheduled chunk (0 selects an automatic value).

Definition at line 1240 of file ntt.H.

References ah_invalid_argument_if, Aleph::NTT< MOD, ROOT >::Plan::apply_transform(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::n_, Aleph::ThreadPool::num_threads(), Aleph::parallel_for_index(), Aleph::NTT< MOD, ROOT >::Plan::size(), and Aleph::NTT< MOD, ROOT >::standard.

Referenced by Aleph::NTT< MOD, ROOT >::ptransform_batch(), and Aleph::NTT< MOD, ROOT >::Plan::ptransformed_batch().

ptransformed()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array< uint64_t > Aleph::NTT< MOD, ROOT >::Plan::ptransformed ( ThreadPool &  pool, const Array< uint64_t > &  input, const bool  invert = false, const size_t  chunk_size = 0  ) const

inline

Parallel transform returning a new array.

Parameters

pool	Thread pool used for stage-level parallelism.
input	Input array. Its size must equal the plan size.
invert	If true, computes the inverse NTT.
chunk_size	Iterations per scheduled chunk (0 selects an automatic value).

Returns

Transformed copy of input.

Definition at line 1177 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), output, and Aleph::NTT< MOD, ROOT >::Plan::ptransform().

ptransformed_batch()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array< Array< uint64_t > > Aleph::NTT< MOD, ROOT >::Plan::ptransformed_batch ( ThreadPool &  pool, const Array< Array< uint64_t > > &  input, const bool  invert = false, const size_t  chunk_size = 0  ) const

inline

Return a parallel-transformed copy of an entire batch.

Parameters

pool	Thread pool used for execution.
input	Batch of arrays; every item must match the plan size.
invert	If true, computes inverse transforms.
chunk_size	Iterations per scheduled chunk (0 selects an automatic value).

Returns

Transformed batch.

Definition at line 1299 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), output, and Aleph::NTT< MOD, ROOT >::Plan::ptransform_batch().

scale_inverse()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::scale_inverse ( Array< uint64_t > &  a, ThreadPool *const  pool, const size_t  chunk_size  ) const

inlineprivate

Definition at line 835 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::for_each_index(), Aleph::NTT< MOD, ROOT >::Plan::inv_n_, Aleph::NTT< MOD, ROOT >::mctx_, and Aleph::NTT< MOD, ROOT >::Plan::n_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_transform().

should_use_avx2()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

bool Aleph::NTT< MOD, ROOT >::Plan::should_use_avx2 ( ThreadPool *const  pool ) const

inlineprivatenoexcept

Definition at line 529 of file ntt.H.

References Aleph::and, Aleph::NTT< MOD, ROOT >::avx2, Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::power_of_two, Aleph::NTT< MOD, ROOT >::simd_backend(), Aleph::NTT< MOD, ROOT >::simd_mod_supported(), and Aleph::NTT< MOD, ROOT >::Plan::strategy_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies().

should_use_neon()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

bool Aleph::NTT< MOD, ROOT >::Plan::should_use_neon ( ThreadPool *const  pool ) const

inlineprivatenoexcept

Definition at line 546 of file ntt.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::neon, Aleph::NTT< MOD, ROOT >::Plan::power_of_two, Aleph::NTT< MOD, ROOT >::simd_backend(), Aleph::NTT< MOD, ROOT >::simd_mod_supported(), and Aleph::NTT< MOD, ROOT >::Plan::strategy_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies().

size()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

size_t Aleph::NTT< MOD, ROOT >::Plan::size ( ) const

inlinenoexcept

Return the transform size bound to the plan.

Definition at line 1097 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::n_.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::ptransform_batch(), and Aleph::NTT< MOD, ROOT >::Plan::transform_batch().

transform()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::transform ( Array< uint64_t > &  a, const bool  invert  ) const

inline

In-place forward or inverse transform.

Parameters

a	Input/output array. Its size must equal the plan size.
invert	If true, computes the inverse NTT.

Definition at line 1108 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::Plan::apply_transform(), Aleph::divide_and_conquer_partition_dp(), and Aleph::NTT< MOD, ROOT >::standard.

Referenced by Aleph::NTT< MOD, ROOT >::transform(), and Aleph::NTT< MOD, ROOT >::Plan::transformed().

transform_batch()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

void Aleph::NTT< MOD, ROOT >::Plan::transform_batch ( Array< Array< uint64_t > > &  batch, const bool  invert  ) const

inline

Sequential batch transform for equal-sized inputs.

Parameters

batch	Batch of arrays; every item must match the plan size.
invert	If true, computes inverse transforms.

Definition at line 1212 of file ntt.H.

References ah_invalid_argument_if, Aleph::NTT< MOD, ROOT >::Plan::apply_transform(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::Plan::n_, Aleph::NTT< MOD, ROOT >::Plan::size(), and Aleph::NTT< MOD, ROOT >::standard.

Referenced by Aleph::NTT< MOD, ROOT >::transform_batch(), and Aleph::NTT< MOD, ROOT >::Plan::transformed_batch().

transformed()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array< uint64_t > Aleph::NTT< MOD, ROOT >::Plan::transformed ( const Array< uint64_t > &  input, const bool  invert = false  ) const

inline

Transform an input array and return the result.

Parameters

input	Input array. Its size must equal the plan size.
invert	If true, computes the inverse NTT.

Returns

Transformed copy of input.

Definition at line 1124 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), output, and Aleph::NTT< MOD, ROOT >::Plan::transform().

transformed_batch()

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array< Array< uint64_t > > Aleph::NTT< MOD, ROOT >::Plan::transformed_batch ( const Array< Array< uint64_t > > &  input, const bool  invert = false  ) const

inline

Return a transformed copy of an entire batch.

Parameters

input	Batch of arrays; every item must match the plan size.
invert	If true, computes inverse transforms.

Returns

Transformed batch.

Definition at line 1281 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), output, and Aleph::NTT< MOD, ROOT >::Plan::transform_batch().

Referenced by Aleph::NTT< MOD, ROOT >::transformed_batch().

Member Data Documentation

bit_rev_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array<size_t> Aleph::NTT< MOD, ROOT >::Plan::bit_rev_

private

Definition at line 476 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_bit_reversal(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_bit_reversal().

bluestein_chirp_fwd_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array<uint64_t> Aleph::NTT< MOD, ROOT >::Plan::bluestein_chirp_fwd_

private

Definition at line 482 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan().

bluestein_chirp_inv_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array<uint64_t> Aleph::NTT< MOD, ROOT >::Plan::bluestein_chirp_inv_

private

Definition at line 483 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan().

bluestein_kernel_forward_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array<uint64_t> Aleph::NTT< MOD, ROOT >::Plan::bluestein_kernel_forward_

private

Definition at line 484 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan().

bluestein_kernel_inverse_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array<uint64_t> Aleph::NTT< MOD, ROOT >::Plan::bluestein_kernel_inverse_

private

Definition at line 485 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan().

bluestein_plan_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

std::shared_ptr<const Plan> Aleph::NTT< MOD, ROOT >::Plan::bluestein_plan_

private

Definition at line 486 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan().

bluestein_size_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

size_t Aleph::NTT< MOD, ROOT >::Plan::bluestein_size_ = 0

private

Definition at line 481 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan().

inv_n_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

uint64_t Aleph::NTT< MOD, ROOT >::Plan::inv_n_ = 0

private

Definition at line 479 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::initialize_power_of_two_plan(), and Aleph::NTT< MOD, ROOT >::Plan::scale_inverse().

inv_n_std_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

uint64_t Aleph::NTT< MOD, ROOT >::Plan::inv_n_std_ = 1

private

Definition at line 480 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::Plan(), and Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform().

log_n_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

size_t Aleph::NTT< MOD, ROOT >::Plan::log_n_ = 0

private

Definition at line 475 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies_scalar(), Aleph::NTT< MOD, ROOT >::Plan::initialize_power_of_two_plan(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_twiddles().

n_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

size_t Aleph::NTT< MOD, ROOT >::Plan::n_ = 0

private

Definition at line 474 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::Plan(), Aleph::NTT< MOD, ROOT >::Plan::apply_bit_reversal(), Aleph::NTT< MOD, ROOT >::Plan::apply_bluestein_transform(), Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies_scalar(), Aleph::NTT< MOD, ROOT >::Plan::apply_transform(), Aleph::NTT< MOD, ROOT >::Plan::initialize_bit_reversal(), Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan(), Aleph::NTT< MOD, ROOT >::Plan::initialize_power_of_two_plan(), Aleph::NTT< MOD, ROOT >::Plan::initialize_twiddles(), Aleph::NTT< MOD, ROOT >::Plan::lift_input(), Aleph::NTT< MOD, ROOT >::Plan::lower_output(), Aleph::NTT< MOD, ROOT >::Plan::multiply_impl(), Aleph::NTT< MOD, ROOT >::Plan::ptransform_batch(), Aleph::NTT< MOD, ROOT >::Plan::scale_inverse(), Aleph::NTT< MOD, ROOT >::Plan::size(), and Aleph::NTT< MOD, ROOT >::Plan::transform_batch().

strategy_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Strategy Aleph::NTT< MOD, ROOT >::Plan::strategy_ = Strategy::power_of_two

private

Definition at line 473 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_transform(), Aleph::NTT< MOD, ROOT >::Plan::initialize_bluestein_plan(), Aleph::NTT< MOD, ROOT >::Plan::initialize_power_of_two_plan(), Aleph::NTT< MOD, ROOT >::Plan::multiply_impl(), Aleph::NTT< MOD, ROOT >::Plan::should_use_avx2(), and Aleph::NTT< MOD, ROOT >::Plan::should_use_neon().

twiddles_fwd_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array<uint64_t> Aleph::NTT< MOD, ROOT >::Plan::twiddles_fwd_

private

Definition at line 477 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_twiddles().

twiddles_inv_

template<uint64_t MOD = 998244353ULL, uint64_t ROOT = 3ULL>

Array<uint64_t> Aleph::NTT< MOD, ROOT >::Plan::twiddles_inv_

private

Definition at line 478 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_butterflies(), and Aleph::NTT< MOD, ROOT >::Plan::initialize_twiddles().

---

The documentation for this class was generated from the following file:

• ntt.H