Number Theoretic Transform over Z / MOD Z. More...

#include <ntt.H>

Classes
class	Plan
	Precomputed plans for NTT transforms. More...

Public Types
enum class	NTTSimdBackend { scalar , avx2 , neon }
	SIMD backends available to the NTT butterfly core. More...

Static Public Member Functions
static constexpr const char *	simd_backend_name (const NTTSimdBackend backend) noexcept

static bool	avx2_dispatch_available () noexcept
	Returns whether AVX2 dispatch is available at runtime.

static bool	neon_dispatch_available () noexcept
	Returns whether AArch64 NEON dispatch is available at runtime.

static NTTSimdBackend	simd_backend () noexcept
	Returns the SIMD backend selected under `ALEPH_NTT_SIMD`.

static const char *	simd_backend_name () noexcept
	Returns the active SIMD backend name.

static constexpr uint64_t	max_transform_size () noexcept
	Maximum supported power-of-two transform size.

static constexpr bool	supports_size (const size_t n) noexcept
	Check whether a transform size is supported.

static constexpr uint64_t	primitive_root_of_unity (const size_t n)
	Return an `n`-th primitive root of unity modulo `MOD`.

static void	transform (Array< uint64_t > &a, const bool invert)
	In-place forward or inverse transform.

static Array< uint64_t >	transformed (const Array< uint64_t > &input, const bool invert=false)
	Transform an input array and return the result.

static Array< uint64_t >	multiply (const Array< uint64_t > &a, const Array< uint64_t > &b)
	Multiply two polynomials modulo `MOD`.

static void	multiply_inplace (Array< uint64_t > &a, const Array< uint64_t > &b)
	Replace `a` by the product `a * b`.

static Array< uint64_t >	negacyclic_multiply (const Array< uint64_t > &a, const Array< uint64_t > &b)
	Negacyclic convolution modulo `x^N + 1`.

static void	transform_batch (Array< Array< uint64_t > > &batch, const bool invert)
	Sequential batch transform for equal-sized inputs.

static Array< Array< uint64_t > >	transformed_batch (const Array< Array< uint64_t > > &batch, const bool invert=false)
	Return a transformed copy of an entire batch.

static void	ptransform (ThreadPool &pool, Array< uint64_t > &a, const bool invert, const size_t chunk_size=0)
	Parallel in-place transform using a ThreadPool.

static Array< uint64_t >	ptransformed (ThreadPool &pool, const Array< uint64_t > &input, const bool invert=false, const size_t chunk_size=0)
	Parallel transform returning a new array.

static Array< uint64_t >	pmultiply (ThreadPool &pool, const Array< uint64_t > &a, const Array< uint64_t > &b, const size_t chunk_size=0)
	Parallel polynomial multiplication modulo `MOD`.

static void	ptransform_batch (ThreadPool &pool, Array< Array< uint64_t > > &batch, const bool invert, const size_t chunk_size=0)
	Parallel batch transform for equal-sized inputs.

static uint64_t	poly_eval (const Array< uint64_t > &coeffs, const uint64_t x)
	Evaluate a polynomial at a single point modulo `MOD`.

static Array< uint64_t >	poly_inverse (const Array< uint64_t > &coeffs, const size_t n)
	Formal polynomial inverse modulo `x^n`.

static std::pair< Array< uint64_t >, Array< uint64_t > >	poly_divmod (const Array< uint64_t > &dividend, const Array< uint64_t > &divisor)
	Polynomial division with remainder modulo `MOD`.

static Array< uint64_t >	poly_log (const Array< uint64_t > &coeffs, const size_t n)
	Formal polynomial logarithm modulo `x^n`.

static Array< uint64_t >	poly_exp (const Array< uint64_t > &coeffs, const size_t n)
	Formal polynomial exponential modulo `x^n`.

static Array< uint64_t >	poly_sqrt (const Array< uint64_t > &coeffs, const size_t n)
	Formal polynomial square root modulo `x^n`.

static Array< uint64_t >	poly_power (const Array< uint64_t > &coeffs, const uint64_t k, const size_t n)
	Formal polynomial power modulo `x^n`.

static Array< uint64_t >	multipoint_eval (const Array< uint64_t > &coeffs, const Array< uint64_t > &points)
	Evaluate a polynomial on multiple points modulo `MOD`.

static Array< uint64_t >	interpolate (const Array< uint64_t > &points, const Array< uint64_t > &values)
	Interpolate a polynomial from point-value samples modulo `MOD`.

template<uint64_t Base = (1ULL << 15)>
static Array< uint64_t >	bigint_multiply (const Array< uint64_t > &a, const Array< uint64_t > &b)
	Multiply two non-negative integers represented as base-`Base` digits.

template<uint64_t Base = (1ULL << 15)>
static Array< uint64_t >	pbigint_multiply (ThreadPool &pool, const Array< uint64_t > &a, const Array< uint64_t > &b, const size_t chunk_size=0)
	Parallel big-integer multiplication in base `Base`.

Static Public Attributes
static constexpr uint64_t	mod = MOD

static constexpr uint64_t	root = ROOT

Private Types
enum class	SimdPreference { automatic , scalar_only , avx2_only , neon_only }

enum class	Representation { standard , montgomery }

Static Private Member Functions
static constexpr bool	is_power_of_two (const size_t n) noexcept

static constexpr uint64_t	add_mod (const uint64_t lhs, const uint64_t rhs) noexcept

static constexpr uint64_t	sub_mod (const uint64_t lhs, const uint64_t rhs) noexcept

static constexpr bool	simd_mod_supported () noexcept

static constexpr uint64_t	pow_mod_constexpr (uint64_t base, uint64_t exp) noexcept

static constexpr uint64_t	max_transform_size_impl () noexcept

static constexpr bool	supports_power_of_two_size (const size_t n) noexcept

static constexpr bool	supports_root_order (const uint64_t order) noexcept

static constexpr bool	supports_bluestein_size (const size_t n) noexcept

static void	validate_root_order (const uint64_t order, const char *const ctx)

static constexpr uint64_t	primitive_root_of_order (const uint64_t order)

static void	validate_supported_size (const size_t n, const char *const ctx)

static size_t	next_power_of_two (size_t n, const char *const ctx)

static Array< uint64_t >	padded_copy (const Array< uint64_t > &input, const size_t n)

static Array< uint64_t >	prefix_copy (const Array< uint64_t > &input, const size_t length)

static constexpr const char *	simd_preference_name (const SimdPreference preference) noexcept

static SimdPreference	simd_preference () noexcept

static NTTSimdBackend	detected_simd_backend () noexcept

static void	trim_trailing_zeros (Array< uint64_t > &poly)

static Array< uint64_t >	normalize_poly (const Array< uint64_t > &input)

static Array< uint64_t >	zero_series (const size_t n)

static Array< uint64_t >	series_prefix (const Array< uint64_t > &input, const size_t n)

static Array< uint64_t >	truncate_poly (const Array< uint64_t > &input, const size_t n)

static Array< uint64_t >	reverse_poly (const Array< uint64_t > &input)

static Array< uint64_t >	poly_add_series (const Array< uint64_t > &lhs, const Array< uint64_t > &rhs, const size_t n)

static Array< uint64_t >	poly_sub_series (const Array< uint64_t > &lhs, const Array< uint64_t > &rhs, const size_t n)

static Array< uint64_t >	poly_add_normalized (const Array< uint64_t > &lhs, const Array< uint64_t > &rhs)

static Array< uint64_t >	poly_sub_normalized (const Array< uint64_t > &lhs, const Array< uint64_t > &rhs)

static Array< uint64_t >	poly_scalar_mul_series (const Array< uint64_t > &input, const uint64_t scalar, const size_t n)

static Array< uint64_t >	poly_mul_trunc (const Array< uint64_t > &lhs, const Array< uint64_t > &rhs, const size_t n)

static Array< uint64_t >	poly_derivative (const Array< uint64_t > &coeffs)

static Array< uint64_t >	poly_integral (const Array< uint64_t > &coeffs)

static uint64_t	tonelli_shanks (const uint64_t value, const char *const ctx)

static Array< Array< uint64_t > >	make_product_tree_storage (const size_t count)

static void	build_product_tree (Array< Array< uint64_t > > &tree, const Array< uint64_t > &points, const size_t node, const size_t left, const size_t right)

static void	validate_distinct_points (const Array< uint64_t > &points, const char *const ctx)

static Array< uint64_t >	poly_mod (const Array< uint64_t > &dividend, const Array< uint64_t > &divisor)

static void	multipoint_eval_recursive (const Array< Array< uint64_t > > &tree, const Array< uint64_t > &poly, Array< uint64_t > &output, const size_t node, const size_t left, const size_t right)

static Array< uint64_t >	interpolate_recursive (const Array< Array< uint64_t > > &tree, const Array< uint64_t > &scaled_values, const size_t node, const size_t left, const size_t right)

Static Private Attributes
static constexpr MontgomeryCtx	mctx_ = montgomery_ctx_for_mod<MOD>()

Detailed Description

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

Number Theoretic Transform over Z / MOD Z.

The implementation mirrors the iterative Cooley-Tukey structure used in Aleph's FFT support, but replaces floating-point arithmetic with exact modular operations. Internally, multiplications are carried out in the Montgomery domain for a fixed odd modulus.

Current capabilities:

power-of-two transforms
Bluestein-based transforms for supported non-power-of-two sizes
AVX2/NEON runtime dispatch on the power-of-two butterfly path
reusable plans
batch transforms
explicit ThreadPool parallelism
fast polynomial multiplication modulo MOD
exact big-integer multiplication over base-B digits
negacyclic convolution modulo x^N + 1

Template Parameters

MOD Prime modulus with a sufficiently large power-of-two factor in MOD - 1.

ROOT Primitive root modulo MOD.

Definition at line 114 of file ntt.H.

Member Enumeration Documentation

◆ NTTSimdBackend

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

enum class Aleph::NTT::NTTSimdBackend

strong

SIMD backends available to the NTT butterfly core.

Enumerator
scalar	Portable scalar implementation.
avx2	x86-64 AVX2 grouped butterfly path.
neon	AArch64 NEON grouped butterfly path.

Definition at line 122 of file ntt.H.

◆ Representation

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

enum class Aleph::NTT::Representation

strongprivate

Enumerator
standard
montgomery

Definition at line 138 of file ntt.H.

◆ SimdPreference

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

enum class Aleph::NTT::SimdPreference

strongprivate

Enumerator
automatic
scalar_only
avx2_only
neon_only

Definition at line 130 of file ntt.H.

Member Function Documentation

◆ add_mod()

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

static constexpr uint64_t Aleph::NTT< MOD, ROOT >::add_mod	(	const uint64_t	lhs,
		const uint64_t	rhs
	)

inlinestaticconstexprprivatenoexcept

Definition at line 153 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), MOD, and Aleph::sum().

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_scalar_butterfly_range(), Aleph::NTT< MOD, ROOT >::poly_add_series(), Aleph::NTT< MOD, ROOT >::poly_eval(), and Aleph::NTT< MOD, ROOT >::poly_exp().

◆ avx2_dispatch_available()

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

static bool Aleph::NTT< MOD, ROOT >::avx2_dispatch_available ( )

inlinestaticnoexcept

Returns whether AVX2 dispatch is available at runtime.

Definition at line 397 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp().

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

◆ bigint_multiply()

template<uint64_t MOD, uint64_t ROOT>

template<uint64_t Base>

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

static

Multiply two non-negative integers represented as base-Base digits.

Digits are stored in little-endian order: a[0] is the least significant digit. The result is normalized by trimming high zero digits, except that zero is returned as a single digit {0}.

The implementation selects an exact convolution path automatically:

if min(a.size(), b.size()) * (Base - 1)^2 < MOD and the transform size is supported by this NTT<MOD, ROOT>, a single-prime exact multiplication is used
otherwise it falls back to NTTExact, then propagates carries

Template Parameters

Base	Digit base, must be at least 2.

Parameters

a	First integer digits.
b	Second integer digits.

Returns: Exact product digits in base Base.

Exceptions

std::invalid_argument if some input digit is outside [0, Base) or if no exact backend can support the requested convolution.

Definition at line 2740 of file ntt.H.

References ah_invalid_argument_if, Aleph::and, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), MOD, Aleph::NTTExact::multiply(), output, Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

◆ build_product_tree()

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

static void Aleph::NTT< MOD, ROOT >::build_product_tree	(	Array< Array< uint64_t > > &	tree,
		const Array< uint64_t > &	points,
		const size_t	node,
		const size_t	left,
		const size_t	right
	)

inlinestaticprivate

Definition at line 1550 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::build_product_tree(), Aleph::divide_and_conquer_partition_dp(), MOD, Aleph::NTT< MOD, ROOT >::multiply(), and Aleph::NTT< MOD, ROOT >::sub_mod().

Referenced by Aleph::NTT< MOD, ROOT >::build_product_tree(), Aleph::NTT< MOD, ROOT >::interpolate(), and Aleph::NTT< MOD, ROOT >::multipoint_eval().

◆ detected_simd_backend()

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

static NTTSimdBackend Aleph::NTT< MOD, ROOT >::detected_simd_backend ( )

inlinestaticprivatenoexcept

Definition at line 385 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::avx2, Aleph::NTT< MOD, ROOT >::avx2_dispatch_available(), Aleph::NTT< MOD, ROOT >::neon, Aleph::NTT< MOD, ROOT >::neon_dispatch_available(), and Aleph::NTT< MOD, ROOT >::scalar.

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

◆ interpolate()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::interpolate	(	const Array< uint64_t > &	points,
		const Array< uint64_t > &	values
	)

inlinestatic

Interpolate a polynomial from point-value samples modulo MOD.

Parameters

points	Sample points.
values	Sample values.

Returns: Unique polynomial of degree < points.size() passing through all pairs.

Exceptions

std::invalid_argument if the points collide modulo MOD or the arrays have different sizes.

Definition at line 2272 of file ntt.H.

References ah_invalid_argument_if, Aleph::NTT< MOD, ROOT >::build_product_tree(), Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::interpolate_recursive(), Aleph::Array< T >::is_empty(), Aleph::NTT< MOD, ROOT >::make_product_tree_storage(), MOD, Aleph::mod_inv(), Aleph::mod_mul(), Aleph::NTT< MOD, ROOT >::multipoint_eval(), Aleph::NTT< MOD, ROOT >::normalize_poly(), Aleph::NTT< MOD, ROOT >::poly_derivative(), Aleph::Array< T >::size(), and Aleph::NTT< MOD, ROOT >::validate_distinct_points().

◆ interpolate_recursive()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::interpolate_recursive	(	const Array< Array< uint64_t > > &	tree,
		const Array< uint64_t > &	scaled_values,
		const size_t	node,
		const size_t	left,
		const size_t	right
	)

inlinestaticprivate

Definition at line 1629 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::interpolate_recursive(), MOD, Aleph::NTT< MOD, ROOT >::multiply(), and Aleph::NTT< MOD, ROOT >::poly_add_normalized().

Referenced by Aleph::NTT< MOD, ROOT >::interpolate(), and Aleph::NTT< MOD, ROOT >::interpolate_recursive().

◆ is_power_of_two()

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

static constexpr bool Aleph::NTT< MOD, ROOT >::is_power_of_two ( const size_t n )

inlinestaticconstexprprivatenoexcept

Definition at line 147 of file ntt.H.

References Aleph::and.

Referenced by Aleph::NTT< MOD, ROOT >::negacyclic_multiply(), Aleph::NTT< MOD, ROOT >::supports_bluestein_size(), and Aleph::NTT< MOD, ROOT >::supports_power_of_two_size().

◆ make_product_tree_storage()

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

static Array< Array< uint64_t > > Aleph::NTT< MOD, ROOT >::make_product_tree_storage ( const size_t count )

inlinestaticprivate

Definition at line 1539 of file ntt.H.

References Aleph::Array< T >::append(), Aleph::count(), and Aleph::Array< T >::reserve().

Referenced by Aleph::NTT< MOD, ROOT >::interpolate(), and Aleph::NTT< MOD, ROOT >::multipoint_eval().

◆ max_transform_size()

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

static constexpr uint64_t Aleph::NTT< MOD, ROOT >::max_transform_size ( )

inlinestaticconstexprnoexcept

Maximum supported power-of-two transform size.

Returns: Largest 2^k such that 2^k divides MOD - 1.

Definition at line 1656 of file ntt.H.

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

Referenced by Aleph::NTT< MOD, ROOT >::negacyclic_multiply(), and Aleph::NTT< MOD, ROOT >::validate_supported_size().

◆ max_transform_size_impl()

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

static constexpr uint64_t Aleph::NTT< MOD, ROOT >::max_transform_size_impl ( )

inlinestaticconstexprprivatenoexcept

Definition at line 196 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), MOD, and Aleph::size().

Referenced by Aleph::NTT< MOD, ROOT >::max_transform_size(), and Aleph::NTT< MOD, ROOT >::supports_power_of_two_size().

◆ multiply()

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

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

inlinestatic

Multiply two polynomials modulo MOD.

Parameters

a	First polynomial.
b	Second polynomial.

Returns: Discrete convolution of a and b modulo MOD.

Exceptions

std::invalid_argument if the required transform size is not supported by the modulus.

Definition at line 1729 of file ntt.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), Aleph::NTT< MOD, ROOT >::Plan::multiply(), Aleph::NTT< MOD, ROOT >::next_power_of_two(), Aleph::Array< T >::size(), Aleph::NTT< MOD, ROOT >::supports_size(), and Aleph::NTT< MOD, ROOT >::validate_supported_size().

Referenced by Aleph::NTT< MOD, ROOT >::build_product_tree(), demo_ntt(), Aleph::NTT< MOD, ROOT >::interpolate_recursive(), Aleph::NTT< MOD, ROOT >::multiply_inplace(), Aleph::NTT< MOD, ROOT >::poly_divmod(), Aleph::NTT< MOD, ROOT >::poly_mul_trunc(), and TEST_F().

◆ multiply_inplace()

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

static void Aleph::NTT< MOD, ROOT >::multiply_inplace	(	Array< uint64_t > &	a,
		const Array< uint64_t > &	b
	)

inlinestatic

Replace a by the product a * b.

Parameters

a	Left polynomial, overwritten with the product.
b	Right polynomial.

Definition at line 1756 of file ntt.H.

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

◆ multipoint_eval()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::multipoint_eval	(	const Array< uint64_t > &	coeffs,
		const Array< uint64_t > &	points
	)

inlinestatic

Evaluate a polynomial on multiple points modulo MOD.

Parameters

coeffs	Polynomial coefficients.
points	Evaluation points.

Returns: Values coeffs(points[i]) mod MOD.

Definition at line 2240 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::build_product_tree(), Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), Aleph::NTT< MOD, ROOT >::make_product_tree_storage(), MOD, Aleph::NTT< MOD, ROOT >::multipoint_eval_recursive(), Aleph::NTT< MOD, ROOT >::normalize_poly(), output, and Aleph::Array< T >::size().

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

◆ multipoint_eval_recursive()

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

static void Aleph::NTT< MOD, ROOT >::multipoint_eval_recursive	(	const Array< Array< uint64_t > > &	tree,
		const Array< uint64_t > &	poly,
		Array< uint64_t > &	output,
		const size_t	node,
		const size_t	left,
		const size_t	right
	)

inlinestaticprivate

Definition at line 1599 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), MOD, Aleph::NTT< MOD, ROOT >::multipoint_eval_recursive(), output, Aleph::NTT< MOD, ROOT >::poly_mod(), Aleph::Array< T >::size(), and Aleph::size().

Referenced by Aleph::NTT< MOD, ROOT >::multipoint_eval(), and Aleph::NTT< MOD, ROOT >::multipoint_eval_recursive().

◆ negacyclic_multiply()

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

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

inlinestatic

Negacyclic convolution modulo x^N + 1.

This computes polynomial multiplication in the quotient ring Z / MOD Z [x] / (x^N + 1) using the classic twist/untwist reduction to an N-point NTT. A primitive 2N-th root of unity must therefore exist under the current modulus.

Parameters

a	First polynomial coefficients, size `N`.
b	Second polynomial coefficients, size `N`.

Returns: Negacyclic product of size N.

Exceptions

std::invalid_argument if the inputs have different sizes, if N is not a positive power of two, or if 2N is unsupported by the modulus.

Definition at line 1777 of file ntt.H.

References ah_invalid_argument_if, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), Aleph::NTT< MOD, ROOT >::is_power_of_two(), Aleph::NTT< MOD, ROOT >::max_transform_size(), MOD, Aleph::mod_inv(), Aleph::mod_mul(), Aleph::NTT< MOD, ROOT >::primitive_root_of_unity(), and Aleph::Array< T >::size().

Referenced by TEST_F().

◆ neon_dispatch_available()

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

static bool Aleph::NTT< MOD, ROOT >::neon_dispatch_available ( )

inlinestaticnoexcept

Returns whether AArch64 NEON dispatch is available at runtime.

Definition at line 413 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp().

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

◆ next_power_of_two()

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

static size_t Aleph::NTT< MOD, ROOT >::next_power_of_two	(	size_t	n,
		const char *const	ctx
	)

inlinestaticprivate

Definition at line 282 of file ntt.H.

References ah_overflow_error_if.

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

◆ normalize_poly()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::normalize_poly ( const Array< uint64_t > & input )

inlinestaticprivate

Definition at line 1319 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), MOD, output, Aleph::Array< T >::reserve(), and Aleph::NTT< MOD, ROOT >::trim_trailing_zeros().

Referenced by Aleph::NTT< MOD, ROOT >::interpolate(), Aleph::NTT< MOD, ROOT >::multipoint_eval(), and Aleph::NTT< MOD, ROOT >::poly_divmod().

◆ padded_copy()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::padded_copy	(	const Array< uint64_t > &	input,
		const size_t	n
	)

inlinestaticprivate

Definition at line 301 of file ntt.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), MOD, and output.

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

◆ pbigint_multiply()

template<uint64_t MOD, uint64_t ROOT>

template<uint64_t Base>

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

static

Parallel big-integer multiplication in base Base.

The expensive convolution runs in parallel using the best exact backend selected by bigint_multiply; carry propagation itself remains a linear pass.

Template Parameters

Base	Digit base, must be at least 2.

Parameters

pool	Thread pool used for the convolution backend.
a	First integer digits.
b	Second integer digits.
chunk_size	Parallel chunk size forwarded to the backend.

Returns: Exact product digits in base Base.

Exceptions

std::invalid_argument if some input digit is outside [0, Base) or if no exact backend can support the requested convolution.

Definition at line 2843 of file ntt.H.

References ah_invalid_argument_if, Aleph::and, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), MOD, output, Aleph::NTTExact::pmultiply(), Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

◆ pmultiply()

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

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

inlinestatic

Parallel polynomial multiplication modulo MOD.

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: Discrete convolution of a and b modulo MOD.

Definition at line 1907 of file ntt.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), Aleph::NTT< MOD, ROOT >::next_power_of_two(), Aleph::NTT< MOD, ROOT >::Plan::pmultiply(), Aleph::Array< T >::size(), Aleph::NTT< MOD, ROOT >::supports_size(), and Aleph::NTT< MOD, ROOT >::validate_supported_size().

◆ poly_add_normalized()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_add_normalized	(	const Array< uint64_t > &	lhs,
		const Array< uint64_t > &	rhs
	)

inlinestaticprivate

Definition at line 1401 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), output, Aleph::NTT< MOD, ROOT >::poly_add_series(), and Aleph::NTT< MOD, ROOT >::trim_trailing_zeros().

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

◆ poly_add_series()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_add_series	(	const Array< uint64_t > &	lhs,
		const Array< uint64_t > &	rhs,
		const size_t	n
	)

inlinestaticprivate

Definition at line 1371 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::add_mod(), Aleph::divide_and_conquer_partition_dp(), MOD, output, Aleph::Array< T >::size(), and Aleph::NTT< MOD, ROOT >::zero_series().

Referenced by Aleph::NTT< MOD, ROOT >::poly_add_normalized(), and Aleph::NTT< MOD, ROOT >::poly_sqrt().

◆ poly_derivative()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_derivative ( const Array< uint64_t > & coeffs )

inlinestaticprivate

Definition at line 1449 of file ntt.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), MOD, Aleph::mod_mul(), output, and Aleph::Array< T >::size().

Referenced by Aleph::NTT< MOD, ROOT >::interpolate(), and Aleph::NTT< MOD, ROOT >::poly_log().

◆ poly_divmod()

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

static std::pair< Array< uint64_t >, Array< uint64_t > > Aleph::NTT< MOD, ROOT >::poly_divmod	(	const Array< uint64_t > &	dividend,
		const Array< uint64_t > &	divisor
	)

inlinestatic

Polynomial division with remainder modulo MOD.

Parameters

dividend	Dividend coefficients in ascending degree order.
divisor	Divisor coefficients in ascending degree order.

Returns: {quotient, remainder} with remainder.degree < divisor.degree.

Exceptions

std::invalid_argument if divisor is the zero polynomial.

Definition at line 2020 of file ntt.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), Aleph::NTT< MOD, ROOT >::multiply(), Aleph::NTT< MOD, ROOT >::normalize_poly(), Aleph::NTT< MOD, ROOT >::poly_inverse(), Aleph::NTT< MOD, ROOT >::poly_mul_trunc(), Aleph::NTT< MOD, ROOT >::poly_sub_normalized(), remainder(), Aleph::NTT< MOD, ROOT >::reverse_poly(), Aleph::Array< T >::size(), Aleph::NTT< MOD, ROOT >::trim_trailing_zeros(), and Aleph::NTT< MOD, ROOT >::truncate_poly().

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

◆ poly_eval()

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

static uint64_t Aleph::NTT< MOD, ROOT >::poly_eval	(	const Array< uint64_t > &	coeffs,
		const uint64_t	x
	)

inlinestatic

Evaluate a polynomial at a single point modulo MOD.

Parameters

coeffs	Polynomial coefficients in ascending degree order.
x	Evaluation point.

Returns: sum coeffs[i] * x^i mod MOD.

Definition at line 1958 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::add_mod(), Aleph::divide_and_conquer_partition_dp(), MOD, Aleph::mod_mul(), and Aleph::Array< T >::size().

◆ poly_exp()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_exp	(	const Array< uint64_t > &	coeffs,
		const size_t	n
	)

inlinestatic

Formal polynomial exponential modulo x^n.

Parameters

coeffs	Input polynomial with zero constant term.
n	Number of coefficients to compute.

Returns: exp(coeffs) mod x^n.

Exceptions

std::invalid_argument if coeffs[0] != 0 (mod MOD).

Definition at line 2084 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::add_mod(), ah_invalid_argument_if, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), m, MOD, Aleph::NTT< MOD, ROOT >::poly_log(), Aleph::NTT< MOD, ROOT >::poly_mul_trunc(), Aleph::NTT< MOD, ROOT >::poly_sub_series(), and Aleph::NTT< MOD, ROOT >::series_prefix().

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

◆ poly_integral()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_integral ( const Array< uint64_t > & coeffs )

inlinestaticprivate

Definition at line 1463 of file ntt.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), MOD, Aleph::mod_inv(), Aleph::mod_mul(), output, and Aleph::Array< T >::size().

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

◆ poly_inverse()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_inverse	(	const Array< uint64_t > &	coeffs,
		const size_t	n
	)

inlinestatic

Formal polynomial inverse modulo x^n.

Parameters

coeffs	Input polynomial.
n	Number of coefficients to compute.

Returns: g such that coeffs * g ≡ 1 (mod x^n, MOD).

Exceptions

std::invalid_argument if the constant term is not invertible.

Definition at line 1979 of file ntt.H.

References ah_invalid_argument_if, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), m, MOD, Aleph::mod_inv(), Aleph::NTT< MOD, ROOT >::poly_mul_trunc(), Aleph::NTT< MOD, ROOT >::series_prefix(), Aleph::NTT< MOD, ROOT >::sub_mod(), Aleph::NTT< MOD, ROOT >::truncate_poly(), and Aleph::NTT< MOD, ROOT >::zero_series().

Referenced by Aleph::NTT< MOD, ROOT >::poly_divmod(), Aleph::NTT< MOD, ROOT >::poly_log(), and Aleph::NTT< MOD, ROOT >::poly_sqrt().

◆ poly_log()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_log	(	const Array< uint64_t > &	coeffs,
		const size_t	n
	)

inlinestatic

Formal polynomial logarithm modulo x^n.

Parameters

coeffs	Input polynomial with constant term 1.
n	Number of coefficients to compute.

Returns: ln(coeffs) mod x^n.

Exceptions

std::invalid_argument if coeffs[0] != 1 (mod MOD).

Definition at line 2056 of file ntt.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), MOD, Aleph::NTT< MOD, ROOT >::poly_derivative(), Aleph::NTT< MOD, ROOT >::poly_integral(), Aleph::NTT< MOD, ROOT >::poly_inverse(), Aleph::NTT< MOD, ROOT >::poly_mul_trunc(), Aleph::NTT< MOD, ROOT >::series_prefix(), Aleph::NTT< MOD, ROOT >::truncate_poly(), and Aleph::NTT< MOD, ROOT >::zero_series().

Referenced by Aleph::NTT< MOD, ROOT >::poly_exp(), and Aleph::NTT< MOD, ROOT >::poly_power().

◆ poly_mod()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_mod	(	const Array< uint64_t > &	dividend,
		const Array< uint64_t > &	divisor
	)

inlinestaticprivate

Definition at line 1583 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::NTT< MOD, ROOT >::poly_divmod().

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

◆ poly_mul_trunc()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_mul_trunc	(	const Array< uint64_t > &	lhs,
		const Array< uint64_t > &	rhs,
		const size_t	n
	)

inlinestaticprivate

Definition at line 1433 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), Aleph::NTT< MOD, ROOT >::multiply(), Aleph::NTT< MOD, ROOT >::series_prefix(), Aleph::NTT< MOD, ROOT >::truncate_poly(), and Aleph::NTT< MOD, ROOT >::zero_series().

Referenced by Aleph::NTT< MOD, ROOT >::poly_divmod(), Aleph::NTT< MOD, ROOT >::poly_exp(), Aleph::NTT< MOD, ROOT >::poly_inverse(), Aleph::NTT< MOD, ROOT >::poly_log(), and Aleph::NTT< MOD, ROOT >::poly_sqrt().

◆ poly_power()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_power	(	const Array< uint64_t > &	coeffs,
		const uint64_t	k,
		const size_t	n
	)

inlinestatic

Formal polynomial power modulo x^n.

Parameters

coeffs	Base polynomial.
k	Non-negative exponent.
n	Number of coefficients to compute.

Returns: coeffs^k mod x^n.

Definition at line 2181 of file ntt.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), k, MOD, Aleph::mod_exp(), Aleph::mod_inv(), Aleph::mod_mul(), output, Aleph::NTT< MOD, ROOT >::poly_exp(), Aleph::NTT< MOD, ROOT >::poly_log(), Aleph::NTT< MOD, ROOT >::poly_scalar_mul_series(), Aleph::Array< T >::reserve(), Aleph::NTT< MOD, ROOT >::truncate_poly(), and Aleph::NTT< MOD, ROOT >::zero_series().

◆ poly_scalar_mul_series()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_scalar_mul_series	(	const Array< uint64_t > &	input,
		const uint64_t	scalar,
		const size_t	n
	)

inlinestaticprivate

Definition at line 1421 of file ntt.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), MOD, Aleph::mod_mul(), output, Aleph::NTT< MOD, ROOT >::scalar, and Aleph::NTT< MOD, ROOT >::zero_series().

Referenced by Aleph::NTT< MOD, ROOT >::poly_power(), and Aleph::NTT< MOD, ROOT >::poly_sqrt().

◆ poly_sqrt()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_sqrt	(	const Array< uint64_t > &	coeffs,
		const size_t	n
	)

inlinestatic

Formal polynomial square root modulo x^n.

Parameters

coeffs	Input polynomial.
n	Number of coefficients to compute.

Returns: g such that g^2 ≡ coeffs (mod x^n, MOD).

Exceptions

std::invalid_argument if no square root exists under the stated preconditions.

Definition at line 2121 of file ntt.H.

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

◆ poly_sub_normalized()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_sub_normalized	(	const Array< uint64_t > &	lhs,
		const Array< uint64_t > &	rhs
	)

inlinestaticprivate

Definition at line 1411 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), output, Aleph::NTT< MOD, ROOT >::poly_sub_series(), and Aleph::NTT< MOD, ROOT >::trim_trailing_zeros().

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

◆ poly_sub_series()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::poly_sub_series	(	const Array< uint64_t > &	lhs,
		const Array< uint64_t > &	rhs,
		const size_t	n
	)

inlinestaticprivate

Definition at line 1386 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), MOD, output, Aleph::Array< T >::size(), Aleph::NTT< MOD, ROOT >::sub_mod(), and Aleph::NTT< MOD, ROOT >::zero_series().

Referenced by Aleph::NTT< MOD, ROOT >::poly_exp(), and Aleph::NTT< MOD, ROOT >::poly_sub_normalized().

◆ pow_mod_constexpr()

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

static constexpr uint64_t Aleph::NTT< MOD, ROOT >::pow_mod_constexpr	(	uint64_t	base,
		uint64_t	exp
	)

inlinestaticconstexprprivatenoexcept

Definition at line 174 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), exp(), and MOD.

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

◆ prefix_copy()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::prefix_copy	(	const Array< uint64_t > &	input,
		const size_t	length
	)

inlinestaticprivate

Definition at line 315 of file ntt.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), output, Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

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

◆ primitive_root_of_order()

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

static constexpr uint64_t Aleph::NTT< MOD, ROOT >::primitive_root_of_order ( const uint64_t order )

inlinestaticconstexprprivate

Definition at line 261 of file ntt.H.

References MOD, Aleph::NTT< MOD, ROOT >::pow_mod_constexpr(), and ROOT.

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

◆ primitive_root_of_unity()

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

static constexpr uint64_t Aleph::NTT< MOD, ROOT >::primitive_root_of_unity ( const size_t n )

inlinestaticconstexpr

Return an n-th primitive root of unity modulo MOD.

Parameters

n	Transform length. It must be a supported power of two.

Returns: Primitive n-th root of unity in standard representation.

Exceptions

std::invalid_argument if n is not supported.

Definition at line 1682 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::primitive_root_of_order(), and Aleph::NTT< MOD, ROOT >::validate_supported_size().

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

◆ ptransform()

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

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

inlinestatic

Parallel in-place transform using a ThreadPool.

Parameters

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

Definition at line 1868 of file ntt.H.

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

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

◆ ptransform_batch()

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

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

inlinestatic

Parallel batch transform for equal-sized inputs.

Parameters

pool	Thread pool used for execution.
batch	Batch of arrays. All items must have the same supported size.
invert	If true, computes inverse transforms.
chunk_size	Iterations per scheduled chunk (0 selects an automatic value).

Definition at line 1940 of file ntt.H.

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

◆ ptransformed()

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

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

inlinestatic

Parallel transform returning a new array.

Parameters

pool	Thread pool used for stage-level parallelism.
input	Input array.
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 1886 of file ntt.H.

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

◆ reverse_poly()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::reverse_poly ( const Array< uint64_t > & input )

inlinestaticprivate

Definition at line 1361 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), MOD, output, and Aleph::Array< T >::reserve().

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

◆ series_prefix()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::series_prefix	(	const Array< uint64_t > &	input,
		const size_t	n
	)

inlinestaticprivate

Definition at line 1339 of file ntt.H.

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

Referenced by Aleph::NTT< MOD, ROOT >::poly_exp(), Aleph::NTT< MOD, ROOT >::poly_inverse(), Aleph::NTT< MOD, ROOT >::poly_log(), Aleph::NTT< MOD, ROOT >::poly_mul_trunc(), and Aleph::NTT< MOD, ROOT >::poly_sqrt().

◆ simd_backend()

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

static NTTSimdBackend Aleph::NTT< MOD, ROOT >::simd_backend ( )

inlinestaticnoexcept

Returns the SIMD backend selected under ALEPH_NTT_SIMD.

Definition at line 432 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::automatic, Aleph::NTT< MOD, ROOT >::avx2, Aleph::NTT< MOD, ROOT >::avx2_only, Aleph::NTT< MOD, ROOT >::detected_simd_backend(), Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::neon, Aleph::NTT< MOD, ROOT >::neon_only, Aleph::NTT< MOD, ROOT >::scalar, Aleph::NTT< MOD, ROOT >::scalar_only, and Aleph::NTT< MOD, ROOT >::simd_preference().

Referenced by Aleph::NTT< MOD, ROOT >::Plan::should_use_avx2(), Aleph::NTT< MOD, ROOT >::Plan::should_use_neon(), and Aleph::NTT< MOD, ROOT >::simd_backend_name().

◆ simd_backend_name() [1/2]

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

static const char * Aleph::NTT< MOD, ROOT >::simd_backend_name ( )

inlinestaticnoexcept

Returns the active SIMD backend name.

Definition at line 455 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::simd_backend(), and Aleph::NTT< MOD, ROOT >::simd_backend_name().

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

◆ simd_backend_name() [2/2]

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

static constexpr const char * Aleph::NTT< MOD, ROOT >::simd_backend_name ( const NTTSimdBackend backend )

inlinestaticconstexprnoexcept

Definition at line 334 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::avx2, Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::neon, and Aleph::NTT< MOD, ROOT >::scalar.

◆ simd_mod_supported()

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

static constexpr bool Aleph::NTT< MOD, ROOT >::simd_mod_supported ( )

inlinestaticconstexprprivatenoexcept

Definition at line 168 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp().

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

◆ simd_preference()

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

static SimdPreference Aleph::NTT< MOD, ROOT >::simd_preference ( )

inlinestaticprivatenoexcept

Definition at line 367 of file ntt.H.

References Aleph::and, Aleph::NTT< MOD, ROOT >::automatic, Aleph::NTT< MOD, ROOT >::avx2_only, Aleph::mode(), Aleph::NTT< MOD, ROOT >::neon_only, and Aleph::NTT< MOD, ROOT >::scalar_only.

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

◆ simd_preference_name()

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

static constexpr const char * Aleph::NTT< MOD, ROOT >::simd_preference_name ( const SimdPreference preference )

inlinestaticconstexprprivatenoexcept

Definition at line 350 of file ntt.H.

References Aleph::NTT< MOD, ROOT >::automatic, Aleph::NTT< MOD, ROOT >::avx2_only, Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::neon_only, and Aleph::NTT< MOD, ROOT >::scalar_only.

◆ sub_mod()

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

static constexpr uint64_t Aleph::NTT< MOD, ROOT >::sub_mod	(	const uint64_t	lhs,
		const uint64_t	rhs
	)

inlinestaticconstexprprivatenoexcept

Definition at line 161 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), and MOD.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_scalar_butterfly_range(), Aleph::NTT< MOD, ROOT >::build_product_tree(), Aleph::NTT< MOD, ROOT >::poly_inverse(), and Aleph::NTT< MOD, ROOT >::poly_sub_series().

◆ supports_bluestein_size()

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

static constexpr bool Aleph::NTT< MOD, ROOT >::supports_bluestein_size ( const size_t n )

inlinestaticconstexprprivatenoexcept

Definition at line 222 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::is_power_of_two(), MOD, Aleph::NTT< MOD, ROOT >::supports_power_of_two_size(), and Aleph::NTT< MOD, ROOT >::supports_root_order().

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

◆ supports_power_of_two_size()

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

static constexpr bool Aleph::NTT< MOD, ROOT >::supports_power_of_two_size ( const size_t n )

inlinestaticconstexprprivatenoexcept

Definition at line 209 of file ntt.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::is_power_of_two(), and Aleph::NTT< MOD, ROOT >::max_transform_size_impl().

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

◆ supports_root_order()

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

static constexpr bool Aleph::NTT< MOD, ROOT >::supports_root_order ( const uint64_t order )

inlinestaticconstexprprivatenoexcept

Definition at line 216 of file ntt.H.

References Aleph::and, and MOD.

Referenced by Aleph::NTT< MOD, ROOT >::supports_bluestein_size(), and Aleph::NTT< MOD, ROOT >::validate_root_order().

◆ supports_size()

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

static constexpr bool Aleph::NTT< MOD, ROOT >::supports_size ( const size_t n )

inlinestaticconstexprnoexcept

Check whether a transform size is supported.

Parameters

n	Candidate transform size.

Returns: true iff n is a positive power of two within the modulus limit.

Definition at line 1668 of file ntt.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::supports_bluestein_size(), and Aleph::NTT< MOD, ROOT >::supports_power_of_two_size().

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

◆ tonelli_shanks()

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

static uint64_t Aleph::NTT< MOD, ROOT >::tonelli_shanks	(	const uint64_t	value,
		const char *const	ctx
	)

inlinestaticprivate

Definition at line 1476 of file ntt.H.

References ah_invalid_argument_if, ah_runtime_error_if, Aleph::and, Aleph::divide_and_conquer_partition_dp(), m, MOD, Aleph::mod_exp(), Aleph::mod_mul(), r, and Aleph::NTT< MOD, ROOT >::root.

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

◆ transform()

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

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

inlinestatic

In-place forward or inverse transform.

Parameters

a	Input/output array.
invert	If true, computes the inverse NTT.

Definition at line 1699 of file ntt.H.

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

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

◆ transform_batch()

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

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

inlinestatic

Sequential batch transform for equal-sized inputs.

Parameters

batch	Batch of arrays. All items must have the same supported size.
invert	If true, computes inverse transforms.

Definition at line 1833 of file ntt.H.

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

◆ transformed()

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

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

inlinestatic

Transform an input array and return the result.

Parameters

input	Input array.
invert	If true, computes the inverse NTT.

Returns: Transformed copy of input.

Definition at line 1712 of file ntt.H.

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

◆ transformed_batch()

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

static Array< Array< uint64_t > > Aleph::NTT< MOD, ROOT >::transformed_batch	(	const Array< Array< uint64_t > > &	batch,
		const bool	invert = `false`
	)

inlinestatic

Return a transformed copy of an entire batch.

Parameters

batch	Batch of arrays. All items must have the same supported size.
invert	If true, computes inverse transforms.

Returns: Transformed batch.

Definition at line 1850 of file ntt.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::size(), and Aleph::NTT< MOD, ROOT >::Plan::transformed_batch().

◆ trim_trailing_zeros()

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

static void Aleph::NTT< MOD, ROOT >::trim_trailing_zeros ( Array< uint64_t > & poly )

inlinestaticprivate

Definition at line 1312 of file ntt.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_last(), Aleph::Array< T >::is_empty(), MOD, and Aleph::Array< T >::remove_last().

Referenced by Aleph::NTT< MOD, ROOT >::normalize_poly(), Aleph::NTT< MOD, ROOT >::poly_add_normalized(), Aleph::NTT< MOD, ROOT >::poly_divmod(), and Aleph::NTT< MOD, ROOT >::poly_sub_normalized().

◆ truncate_poly()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::truncate_poly	(	const Array< uint64_t > &	input,
		const size_t	n
	)

inlinestaticprivate

Definition at line 1350 of file ntt.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), MOD, output, and Aleph::Array< T >::reserve().

Referenced by Aleph::NTT< MOD, ROOT >::poly_divmod(), Aleph::NTT< MOD, ROOT >::poly_inverse(), Aleph::NTT< MOD, ROOT >::poly_log(), Aleph::NTT< MOD, ROOT >::poly_mul_trunc(), Aleph::NTT< MOD, ROOT >::poly_power(), and Aleph::NTT< MOD, ROOT >::poly_sqrt().

◆ validate_distinct_points()

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

static void Aleph::NTT< MOD, ROOT >::validate_distinct_points	(	const Array< uint64_t > &	points,
		const char *const	ctx
	)

inlinestaticprivate

Definition at line 1572 of file ntt.H.

References ah_invalid_argument_if, MOD, and Aleph::Array< T >::size().

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

◆ validate_root_order()

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

static void Aleph::NTT< MOD, ROOT >::validate_root_order	(	const uint64_t	order,
		const char *const	ctx
	)

inlinestaticprivate

Definition at line 250 of file ntt.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), MOD, and Aleph::NTT< MOD, ROOT >::supports_root_order().

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

◆ validate_supported_size()

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

static void Aleph::NTT< MOD, ROOT >::validate_supported_size	(	const size_t	n,
		const char *const	ctx
	)

inlinestaticprivate

Definition at line 267 of file ntt.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::NTT< MOD, ROOT >::max_transform_size(), MOD, and Aleph::NTT< MOD, ROOT >::supports_size().

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

◆ zero_series()

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

static Array< uint64_t > Aleph::NTT< MOD, ROOT >::zero_series ( const size_t n )

inlinestaticprivate

Definition at line 1330 of file ntt.H.

References Aleph::Array< T >::create(), and output.

Referenced by Aleph::NTT< MOD, ROOT >::poly_add_series(), Aleph::NTT< MOD, ROOT >::poly_inverse(), Aleph::NTT< MOD, ROOT >::poly_log(), Aleph::NTT< MOD, ROOT >::poly_mul_trunc(), Aleph::NTT< MOD, ROOT >::poly_power(), Aleph::NTT< MOD, ROOT >::poly_scalar_mul_series(), Aleph::NTT< MOD, ROOT >::poly_sqrt(), Aleph::NTT< MOD, ROOT >::poly_sub_series(), and Aleph::NTT< MOD, ROOT >::series_prefix().

Member Data Documentation

◆ mctx_

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

constexpr MontgomeryCtx Aleph::NTT< MOD, ROOT >::mctx_ = montgomery_ctx_for_mod<MOD>()

staticconstexprprivate

Definition at line 144 of file ntt.H.

Referenced by Aleph::NTT< MOD, ROOT >::Plan::apply_scalar_butterfly_range(), 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(), and Aleph::NTT< MOD, ROOT >::Plan::scale_inverse().

◆ mod

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

constexpr uint64_t Aleph::NTT< MOD, ROOT >::mod = MOD

staticconstexpr

Definition at line 330 of file ntt.H.

◆ root

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

constexpr uint64_t Aleph::NTT< MOD, ROOT >::root = ROOT

staticconstexpr

Definition at line 331 of file ntt.H.

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

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

ntt.H

MOD	Prime modulus with a sufficiently large power-of-two factor in `MOD - 1`.
ROOT	Primitive root modulo `MOD`.

Classes

Public Types

Static Public Member Functions

Static Public Attributes

Private Types

Static Private Member Functions

Static Private Attributes

Detailed Description

Member Enumeration Documentation

◆ NTTSimdBackend

◆ Representation

◆ SimdPreference

Member Function Documentation

◆ add_mod()

◆ avx2_dispatch_available()

◆ bigint_multiply()

◆ build_product_tree()

◆ detected_simd_backend()

◆ interpolate()

◆ interpolate_recursive()

◆ is_power_of_two()

◆ make_product_tree_storage()

◆ max_transform_size()

◆ max_transform_size_impl()

◆ multiply()

◆ multiply_inplace()

◆ multipoint_eval()

◆ multipoint_eval_recursive()

◆ negacyclic_multiply()

◆ neon_dispatch_available()

◆ next_power_of_two()

◆ normalize_poly()

◆ padded_copy()

◆ pbigint_multiply()

◆ pmultiply()

◆ poly_add_normalized()

◆ poly_add_series()

◆ poly_derivative()

◆ poly_divmod()

◆ poly_eval()

◆ poly_exp()

◆ poly_integral()

◆ poly_inverse()

◆ poly_log()

◆ poly_mod()

◆ poly_mul_trunc()

◆ poly_power()

◆ poly_scalar_mul_series()

◆ poly_sqrt()

◆ poly_sub_normalized()

◆ poly_sub_series()

◆ pow_mod_constexpr()

◆ prefix_copy()

◆ primitive_root_of_order()

◆ primitive_root_of_unity()

◆ ptransform()

◆ ptransform_batch()

◆ ptransformed()

◆ reverse_poly()

◆ series_prefix()

◆ simd_backend()

◆ simd_backend_name() [1/2]

◆ simd_backend_name() [2/2]

◆ simd_mod_supported()

◆ simd_preference()

◆ simd_preference_name()

◆ sub_mod()

◆ supports_bluestein_size()

◆ supports_power_of_two_size()

◆ supports_root_order()

◆ supports_size()

◆ tonelli_shanks()

◆ transform()

◆ transform_batch()

◆ transformed()

◆ transformed_batch()

◆ trim_trailing_zeros()

◆ truncate_poly()

◆ validate_distinct_points()

◆ validate_root_order()