bb::polynomial_arithmetic Namespace Reference

Classes
struct	LagrangeEvaluations

Concepts
concept	SupportsFFT

Typedefs
using	lagrange_evaluations = LagrangeEvaluations< fr >

Functions
uint32_t	reverse_bits (uint32_t x, uint32_t bit_length)
bool	is_power_of_two (uint64_t x)
template<typename Fr >
void	scale_by_generator (Fr *coeffs, Fr *target, const EvaluationDomain< Fr > &domain, const Fr &generator_start, const Fr &generator_shift, const size_t generator_size)
template<typename Fr > requires SupportsFFT<Fr>
void	compute_multiplicative_subgroup (const size_t log2_subgroup_size, const EvaluationDomain< Fr > &src_domain, Fr *subgroup_roots)
template<typename Fr > requires SupportsFFT<Fr>
void	fft_inner_parallel (std::vector< Fr * > coeffs, const EvaluationDomain< Fr > &domain, const Fr &, const std::vector< Fr * > &root_table)
template<typename Fr > requires SupportsFFT<Fr>
void	fft_inner_parallel (Fr *coeffs, Fr *target, const EvaluationDomain< Fr > &domain, const Fr &, const std::vector< Fr * > &root_table)
template<typename Fr > requires SupportsFFT<Fr>
void	fft (Fr *coeffs, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	fft (Fr *coeffs, Fr *target, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	fft (std::vector< Fr * > coeffs, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	ifft (Fr *coeffs, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	ifft (Fr *coeffs, Fr *target, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	ifft (std::vector< Fr * > coeffs, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	coset_fft (Fr *coeffs, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	coset_fft (Fr *coeffs, Fr *target, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	coset_fft (std::vector< Fr * > coeffs, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	coset_fft (Fr *coeffs, const EvaluationDomain< Fr > &domain, const EvaluationDomain< Fr > &, const size_t domain_extension)
template<typename Fr > requires SupportsFFT<Fr>
void	coset_ifft (Fr *coeffs, const EvaluationDomain< Fr > &domain)
template<typename Fr > requires SupportsFFT<Fr>
void	coset_ifft (std::vector< Fr * > coeffs, const EvaluationDomain< Fr > &domain)
template<typename Fr >
Fr	evaluate (const Fr *coeffs, const Fr &z, const size_t n)
template<typename Fr >
Fr	evaluate (const std::vector< Fr * > coeffs, const Fr &z, const size_t large_n)
fr	compute_barycentric_evaluation (const fr *coeffs, const size_t num_coeffs, const fr &z, const EvaluationDomain< fr > &domain)
template<typename Fr >
Fr	compute_sum (const Fr *src, const size_t n)
template<typename Fr >
void	compute_linear_polynomial_product (const Fr *roots, Fr *dest, const size_t n)
template<typename Fr >
Fr	compute_linear_polynomial_product_evaluation (const Fr *roots, const Fr z, const size_t n)
template<typename Fr >
void	compute_efficient_interpolation (const Fr *src, Fr *dest, const Fr *evaluation_points, const size_t n)
template fr	evaluate< fr > (const fr *, const fr &, const size_t)
template fr	evaluate< fr > (const std::vector< fr * >, const fr &, const size_t)
template void	fft_inner_parallel< fr > (std::vector< fr * >, const EvaluationDomain< fr > &, const fr &, const std::vector< fr * > &)
template void	fft< fr > (fr *, const EvaluationDomain< fr > &)
template void	fft< fr > (fr *, fr *, const EvaluationDomain< fr > &)
template void	fft< fr > (std::vector< fr * >, const EvaluationDomain< fr > &)
template void	coset_fft< fr > (fr *, const EvaluationDomain< fr > &)
template void	coset_fft< fr > (fr *, fr *, const EvaluationDomain< fr > &)
template void	coset_fft< fr > (std::vector< fr * >, const EvaluationDomain< fr > &)
template void	coset_fft< fr > (fr *, const EvaluationDomain< fr > &, const EvaluationDomain< fr > &, const size_t)
template void	ifft< fr > (fr *, const EvaluationDomain< fr > &)
template void	ifft< fr > (fr *, fr *, const EvaluationDomain< fr > &)
template void	ifft< fr > (std::vector< fr * >, const EvaluationDomain< fr > &)
template void	coset_ifft< fr > (fr *, const EvaluationDomain< fr > &)
template void	coset_ifft< fr > (std::vector< fr * >, const EvaluationDomain< fr > &)
template fr	compute_sum< fr > (const fr *, const size_t)
template void	compute_linear_polynomial_product< fr > (const fr *, fr *, const size_t)
template void	compute_efficient_interpolation< fr > (const fr *, fr *, const fr *, const size_t)
template grumpkin::fr	evaluate< grumpkin::fr > (const grumpkin::fr *, const grumpkin::fr &, const size_t)
template grumpkin::fr	evaluate< grumpkin::fr > (const std::vector< grumpkin::fr * >, const grumpkin::fr &, const size_t)
template grumpkin::fr	compute_sum< grumpkin::fr > (const grumpkin::fr *, const size_t)
template void	compute_linear_polynomial_product< grumpkin::fr > (const grumpkin::fr *, grumpkin::fr *, const size_t)
template void	compute_efficient_interpolation< grumpkin::fr > (const grumpkin::fr *, grumpkin::fr *, const grumpkin::fr *, const size_t)
template<typename Fr >
Fr	evaluate (std::span< const Fr > coeffs, const Fr &z, const size_t n)
template<typename Fr >
Fr	evaluate (std::span< const Fr > coeffs, const Fr &z)
fr	compute_barycentric_evaluation (const fr *coeffs, unsigned long num_coeffs, const fr &z, const EvaluationDomain< fr > &domain)
template<typename Fr >
void	factor_roots (std::span< Fr > polynomial, const Fr &root)
	Divides p(X) by (X-r) in-place.

Typedef Documentation

lagrange_evaluations

using bb::polynomial_arithmetic::lagrange_evaluations = typedef LagrangeEvaluations<fr>

Definition at line 21 of file polynomial_arithmetic.hpp.

Function Documentation

compute_barycentric_evaluation() [1/2]

fr bb::polynomial_arithmetic::compute_barycentric_evaluation	(	const fr *	coeffs,
		const size_t	num_coeffs,
		const fr &	z,
		const EvaluationDomain< fr > &	domain
	)

Definition at line 570 of file polynomial_arithmetic.cpp.

compute_barycentric_evaluation() [2/2]

fr bb::polynomial_arithmetic::compute_barycentric_evaluation	(	const fr *	coeffs,
		unsigned long	num_coeffs,
		const fr &	z,
		const EvaluationDomain< fr > &	domain
	)

compute_efficient_interpolation()

template<typename Fr >

void bb::polynomial_arithmetic::compute_efficient_interpolation	(	const Fr *	src,
		Fr *	dest,
		const Fr *	evaluation_points,
		const size_t	n
	)

Definition at line 657 of file polynomial_arithmetic.cpp.

compute_efficient_interpolation< fr >()

template void bb::polynomial_arithmetic::compute_efficient_interpolation< fr >	(	const fr *	,
		fr *	,
		const fr *	,
		const size_t
	)

compute_efficient_interpolation< grumpkin::fr >()

template void bb::polynomial_arithmetic::compute_efficient_interpolation< grumpkin::fr >	(	const grumpkin::fr *	,
		grumpkin::fr *	,
		const grumpkin::fr *	,
		const size_t
	)

compute_linear_polynomial_product()

template<typename Fr >

void bb::polynomial_arithmetic::compute_linear_polynomial_product	(	const Fr *	roots,
		Fr *	dest,
		const size_t	n
	)

Definition at line 624 of file polynomial_arithmetic.cpp.

compute_linear_polynomial_product< fr >()

template void bb::polynomial_arithmetic::compute_linear_polynomial_product< fr >	(	const fr *	,
		fr *	,
		const size_t
	)

compute_linear_polynomial_product< grumpkin::fr >()

template void bb::polynomial_arithmetic::compute_linear_polynomial_product< grumpkin::fr >	(	const grumpkin::fr *	,
		grumpkin::fr *	,
		const size_t
	)

compute_linear_polynomial_product_evaluation()

template<typename Fr >

Fr bb::polynomial_arithmetic::compute_linear_polynomial_product_evaluation	(	const Fr *	roots,
		const Fr	z,
		const size_t	n
	)

Definition at line 647 of file polynomial_arithmetic.cpp.

compute_multiplicative_subgroup()

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::compute_multiplicative_subgroup	(	const size_t	log2_subgroup_size,
		const EvaluationDomain< Fr > &	src_domain,
		Fr *	subgroup_roots
	)

Compute multiplicative subgroup (g.X)^n.

Compute the subgroup for X in roots of unity of (2^log2_subgroup_size)*n. X^n will loop through roots of unity (2^log2_subgroup_size).

Parameters

log2_subgroup_size	Log_2 of the subgroup size.
src_domain	The domain of size n.
subgroup_roots	Pointer to the array for saving subgroup members.

Definition at line 79 of file polynomial_arithmetic.cpp.

compute_sum()

template<typename Fr >

Fr bb::polynomial_arithmetic::compute_sum	(	const Fr *	src,
		const size_t	n
	)

Definition at line 614 of file polynomial_arithmetic.cpp.

compute_sum< fr >()

template fr bb::polynomial_arithmetic::compute_sum< fr >	(	const fr *	,
		const size_t
	)

compute_sum< grumpkin::fr >()

template grumpkin::fr bb::polynomial_arithmetic::compute_sum< grumpkin::fr >	(	const grumpkin::fr *	,
		const size_t
	)

coset_fft() [1/4]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::coset_fft	(	Fr *	coeffs,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 384 of file polynomial_arithmetic.cpp.

coset_fft() [2/4]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::coset_fft	(	Fr *	coeffs,
		const EvaluationDomain< Fr > &	domain,
		const EvaluationDomain< Fr > &	,
		const size_t	domain_extension
	)

Definition at line 417 of file polynomial_arithmetic.cpp.

coset_fft() [3/4]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::coset_fft	(	Fr *	coeffs,
		Fr *	target,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 392 of file polynomial_arithmetic.cpp.

coset_fft() [4/4]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::coset_fft	(	std::vector< Fr * >	coeffs,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 400 of file polynomial_arithmetic.cpp.

coset_fft< fr >() [1/4]

template void bb::polynomial_arithmetic::coset_fft< fr >	(	fr *	,
		const EvaluationDomain< fr > &
	)

coset_fft< fr >() [2/4]

template void bb::polynomial_arithmetic::coset_fft< fr >	(	fr *	,
		const EvaluationDomain< fr > &	,
		const EvaluationDomain< fr > &	,
		const size_t
	)

coset_fft< fr >() [3/4]

template void bb::polynomial_arithmetic::coset_fft< fr >	(	fr *	,
		fr *	,
		const EvaluationDomain< fr > &
	)

coset_fft< fr >() [4/4]

template void bb::polynomial_arithmetic::coset_fft< fr >	(	std::vector< fr * >	,
		const EvaluationDomain< fr > &
	)

coset_ifft() [1/2]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::coset_ifft	(	Fr *	coeffs,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 478 of file polynomial_arithmetic.cpp.

coset_ifft() [2/2]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::coset_ifft	(	std::vector< Fr * >	coeffs,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 486 of file polynomial_arithmetic.cpp.

coset_ifft< fr >() [1/2]

template void bb::polynomial_arithmetic::coset_ifft< fr >	(	fr *	,
		const EvaluationDomain< fr > &
	)

coset_ifft< fr >() [2/2]

template void bb::polynomial_arithmetic::coset_ifft< fr >	(	std::vector< fr * >	,
		const EvaluationDomain< fr > &
	)

evaluate() [1/4]

template<typename Fr >

Fr bb::polynomial_arithmetic::evaluate	(	const Fr *	coeffs,
		const Fr &	z,
		const size_t	n
	)

Definition at line 502 of file polynomial_arithmetic.cpp.

evaluate() [2/4]

template<typename Fr >

Fr bb::polynomial_arithmetic::evaluate	(	const std::vector< Fr * >	coeffs,
		const Fr &	z,
		const size_t	large_n
	)

Definition at line 529 of file polynomial_arithmetic.cpp.

evaluate() [3/4]

template<typename Fr >

Fr bb::polynomial_arithmetic::evaluate	(	std::span< const Fr >	coeffs,
		const Fr &	z
	)

Definition at line 29 of file polynomial_arithmetic.hpp.

evaluate() [4/4]

template<typename Fr >

Fr bb::polynomial_arithmetic::evaluate	(	std::span< const Fr >	coeffs,
		const Fr &	z,
		const size_t	n
	)

Definition at line 24 of file polynomial_arithmetic.hpp.

evaluate< fr >() [1/2]

template fr bb::polynomial_arithmetic::evaluate< fr >	(	const fr *	,
		const fr &	,
		const size_t
	)

evaluate< fr >() [2/2]

template fr bb::polynomial_arithmetic::evaluate< fr >	(	const std::vector< fr * >	,
		const fr &	,
		const size_t
	)

evaluate< grumpkin::fr >() [1/2]

template grumpkin::fr bb::polynomial_arithmetic::evaluate< grumpkin::fr >	(	const grumpkin::fr *	,
		const grumpkin::fr &	,
		const size_t
	)

evaluate< grumpkin::fr >() [2/2]

template grumpkin::fr bb::polynomial_arithmetic::evaluate< grumpkin::fr >	(	const std::vector< grumpkin::fr * >	,
		const grumpkin::fr &	,
		const size_t
	)

factor_roots()

template<typename Fr >

void bb::polynomial_arithmetic::factor_roots	(	std::span< Fr >	polynomial,
		const Fr &	root
	)

Divides p(X) by (X-r) in-place.

Definition at line 109 of file polynomial_arithmetic.hpp.

fft() [1/3]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::fft	(	Fr *	coeffs,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 325 of file polynomial_arithmetic.cpp.

fft() [2/3]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::fft	(	Fr *	coeffs,
		Fr *	target,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 332 of file polynomial_arithmetic.cpp.

fft() [3/3]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::fft	(	std::vector< Fr * >	coeffs,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 339 of file polynomial_arithmetic.cpp.

fft< fr >() [1/3]

template void bb::polynomial_arithmetic::fft< fr >	(	fr *	,
		const EvaluationDomain< fr > &
	)

fft< fr >() [2/3]

template void bb::polynomial_arithmetic::fft< fr >	(	fr *	,
		fr *	,
		const EvaluationDomain< fr > &
	)

fft< fr >() [3/3]

template void bb::polynomial_arithmetic::fft< fr >	(	std::vector< fr * >	,
		const EvaluationDomain< fr > &
	)

fft_inner_parallel() [1/2]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::fft_inner_parallel	(	Fr *	coeffs,
		Fr *	target,
		const EvaluationDomain< Fr > &	domain,
		const Fr &	,
		const std::vector< Fr * > &	root_table
	)

Definition at line 230 of file polynomial_arithmetic.cpp.

fft_inner_parallel() [2/2]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::fft_inner_parallel	(	std::vector< Fr * >	coeffs,
		const EvaluationDomain< Fr > &	domain,
		const Fr &	,
		const std::vector< Fr * > &	root_table
	)

Definition at line 102 of file polynomial_arithmetic.cpp.

fft_inner_parallel< fr >()

template void bb::polynomial_arithmetic::fft_inner_parallel< fr >	(	std::vector< fr * >	,
		const EvaluationDomain< fr > &	,
		const fr &	,
		const std::vector< fr * > &
	)

ifft() [1/3]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::ifft	(	Fr *	coeffs,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 346 of file polynomial_arithmetic.cpp.

ifft() [2/3]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::ifft	(	Fr *	coeffs,
		Fr *	target,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 356 of file polynomial_arithmetic.cpp.

ifft() [3/3]

template<typename Fr >
requires SupportsFFT<Fr>

void bb::polynomial_arithmetic::ifft	(	std::vector< Fr * >	coeffs,
		const EvaluationDomain< Fr > &	domain
	)

Definition at line 366 of file polynomial_arithmetic.cpp.

ifft< fr >() [1/3]

template void bb::polynomial_arithmetic::ifft< fr >	(	fr *	,
		const EvaluationDomain< fr > &
	)

ifft< fr >() [2/3]

template void bb::polynomial_arithmetic::ifft< fr >	(	fr *	,
		fr *	,
		const EvaluationDomain< fr > &
	)

ifft< fr >() [3/3]

template void bb::polynomial_arithmetic::ifft< fr >	(	std::vector< fr * >	,
		const EvaluationDomain< fr > &
	)

is_power_of_two()

bool bb::polynomial_arithmetic::is_power_of_two ( uint64_t  x )

inline

Definition at line 43 of file polynomial_arithmetic.cpp.

reverse_bits()

uint32_t bb::polynomial_arithmetic::reverse_bits ( uint32_t  x, uint32_t  bit_length  )

inline

Definition at line 34 of file polynomial_arithmetic.cpp.

scale_by_generator()

template<typename Fr >

void bb::polynomial_arithmetic::scale_by_generator	(	Fr *	coeffs,
		Fr *	target,
		const EvaluationDomain< Fr > &	domain,
		const Fr &	generator_start,
		const Fr &	generator_shift,
		const size_t	generator_size
	)

Definition at line 49 of file polynomial_arithmetic.cpp.