Public Types
using	value_type = Fr

using	difference_type = std::ptrdiff_t

using	reference = value_type &

using	pointer = std::shared_ptr< value_type[]>

using	const_pointer = pointer

using	iterator = Fr *

using	const_iterator = Fr const *

using	FF = Fr

Public Member Functions
	Polynomial (size_t initial_size)
	Initialize a Polynomial to size 'initial_size', zeroing memory.

	Polynomial (size_t initial_size, DontZeroMemory flag)
	Initialize a Polynomial to size 'initial_size'. Important: This does NOT zero memory.

	Polynomial (const Polynomial &other)

	Polynomial (const Polynomial &other, size_t target_size)

	Polynomial (Polynomial &&other) noexcept

	Polynomial (std::span< const Fr > coefficients)

	Polynomial (std::span< const Fr > interpolation_points, std::span< const Fr > evaluations)
	Create the degree-(m-1) polynomial T(X) that interpolates the given evaluations. We have T(xⱼ) = yⱼ for j=1,...,m.

Polynomial &	operator= (Polynomial &&other) noexcept

Polynomial &	operator= (std::span< const Fr > coefficients) noexcept

Polynomial &	operator= (const Polynomial &other)

Polynomial	share () const

std::array< uint8_t, 32 >	hash () const

void	clear ()

bool	operator== (Polynomial const &rhs) const

Fr const &	operator[] (const size_t i) const

Fr &	operator[] (const size_t i)

Fr const &	at (const size_t i) const

Fr &	at (const size_t i)

Fr	evaluate (const Fr &z, size_t target_size) const

Fr	evaluate (const Fr &z) const

Fr	compute_barycentric_evaluation (const Fr &z, const EvaluationDomain< Fr > &domain)

Fr	evaluate_from_fft (const EvaluationDomain< Fr > &large_domain, const Fr &z, const EvaluationDomain< Fr > &small_domain)

void	fft (const EvaluationDomain< Fr > &domain)

void	partial_fft (const EvaluationDomain< Fr > &domain, Fr constant=1, bool is_coset=false)

void	coset_fft (const EvaluationDomain< Fr > &domain)

void	coset_fft (const EvaluationDomain< Fr > &domain, const EvaluationDomain< Fr > &large_domain, size_t domain_extension)

void	coset_fft_with_constant (const EvaluationDomain< Fr > &domain, const Fr &constant)

void	coset_fft_with_generator_shift (const EvaluationDomain< Fr > &domain, const Fr &constant)

void	ifft (const EvaluationDomain< Fr > &domain)

void	ifft_with_constant (const EvaluationDomain< Fr > &domain, const Fr &constant)

void	coset_ifft (const EvaluationDomain< Fr > &domain)

Fr	compute_kate_opening_coefficients (const Fr &z)

bool	is_empty () const

Polynomial	shifted () const
	Returns an std::span of the left-shift of self.

void	set_to_right_shifted (std::span< Fr > coeffs_in, size_t shift_size=1)
	Set self to the right shift of input coefficients.

void	add_scaled (std::span< const Fr > other, Fr scaling_factor)
	adds the polynomial q(X) 'other', multiplied by a scaling factor.

Polynomial &	operator+= (std::span< const Fr > other)
	adds the polynomial q(X) 'other'.

Polynomial &	operator-= (std::span< const Fr > other)
	subtracts the polynomial q(X) 'other'.

Polynomial &	operator*= (Fr scaling_factor)
	sets this = p(X) to s⋅p(X)

Fr	evaluate_mle (std::span< const Fr > evaluation_points, bool shift=false) const
	evaluates p(X) = ∑ᵢ aᵢ⋅Xⁱ considered as multi-linear extension p(X₀,…,Xₘ₋₁) = ∑ᵢ aᵢ⋅Lᵢ(X₀,…,Xₘ₋₁) at u = (u₀,…,uₘ₋₁)

Polynomial< Fr >	partial_evaluate_mle (std::span< const Fr > evaluation_points) const
	Partially evaluates in the last k variables a polynomial interpreted as a multilinear extension.

void	factor_roots (std::span< const Fr > roots)
	Divides p(X) by (X-r₁)⋯(X−rₘ) in-place. Assumes that p(rⱼ)=0 for all j.

void	factor_roots (const Fr &root)

iterator	begin ()

iterator	end ()

pointer	data ()

std::span< uint8_t >	byte_span () const

const_iterator	begin () const

const_iterator	end () const

const_pointer	data () const

std::size_t	size () const

std::size_t	capacity () const

Member Typedef Documentation

◆ value_type

template<typename Fr >

using barretenberg::Polynomial< Fr >::value_type = Fr

Implements requirements of std::ranges::contiguous_range and std::ranges::sized_range

Constructor & Destructor Documentation

◆ Polynomial() [1/3]

template<typename Fr >

barretenberg::Polynomial< Fr >::Polynomial ( size_t initial_size )

Initialize a Polynomial to size 'initial_size', zeroing memory.

Constructors / Destructors

Parameters

initial_size The initial size of the polynomial.

◆ Polynomial() [2/3]

template<typename Fr >

barretenberg::Polynomial< Fr >::Polynomial	(	size_t	initial_size,
		DontZeroMemory	flag
	)

Initialize a Polynomial to size 'initial_size'. Important: This does NOT zero memory.

Parameters

initial_size	The initial size of the polynomial.
flag	Signals that we do not zero memory.

◆ Polynomial() [3/3]

template<typename Fr >

barretenberg::Polynomial< Fr >::Polynomial	(	std::span< const Fr >	interpolation_points,
		std::span< const Fr >	evaluations
	)

Create the degree-(m-1) polynomial T(X) that interpolates the given evaluations. We have T(xⱼ) = yⱼ for j=1,...,m.

Parameters

interpolation_points	(x₁,…,xₘ)
evaluations	(y₁,…,yₘ)

Member Function Documentation

◆ add_scaled()

template<typename Fr >

void barretenberg::Polynomial< Fr >::add_scaled	(	std::span< const Fr >	other,
		Fr	scaling_factor
	)

adds the polynomial q(X) 'other', multiplied by a scaling factor.

Parameters

other	q(X)
scaling_factor	scaling factor by which all coefficients of q(X) are multiplied

◆ evaluate_mle()

template<typename Fr >

Fr barretenberg::Polynomial< Fr >::evaluate_mle	(	std::span< const Fr >	evaluation_points,
		bool	shift = `false`
	)		const

evaluates p(X) = ∑ᵢ aᵢ⋅Xⁱ considered as multi-linear extension p(X₀,…,Xₘ₋₁) = ∑ᵢ aᵢ⋅Lᵢ(X₀,…,Xₘ₋₁) at u = (u₀,…,uₘ₋₁)

this function allocates a temporary buffer of size n/2

Parameters

evaluation_points	an MLE evaluation point u = (u₀,…,uₘ₋₁)
shift	evaluates p'(X₀,…,Xₘ₋₁) = 1⋅L₀(X₀,…,Xₘ₋₁) + ∑ᵢ˲₁ aᵢ₋₁⋅Lᵢ(X₀,…,Xₘ₋₁) if true

Returns: Fr p(u₀,…,uₘ₋₁)

◆ factor_roots()

template<typename Fr >

void barretenberg::Polynomial< Fr >::factor_roots ( std::span< const Fr > roots )

inline

Divides p(X) by (X-r₁)⋯(X−rₘ) in-place. Assumes that p(rⱼ)=0 for all j.

we specialize the method when only a single root is given. if one of the roots is 0, then we first factor all other roots. dividing by X requires only a left shift of all coefficient.

Parameters

roots list of roots (r₁,…,rₘ)

◆ fft()

template<typename Fr >
requires polynomial_arithmetic::SupportsFFT<Fr>

void barretenberg::Polynomial< Fr >::fft ( const EvaluationDomain< Fr > & domain )

FFTs

◆ operator*=()

template<typename Fr >

Polynomial< Fr > & barretenberg::Polynomial< Fr >::operator*= ( Fr scaling_factor )

sets this = p(X) to s⋅p(X)

Parameters

scaling_factor s

◆ operator+=()

template<typename Fr >

Polynomial< Fr > & barretenberg::Polynomial< Fr >::operator+= ( std::span< const Fr > other )

adds the polynomial q(X) 'other'.

Parameters

other q(X)

◆ operator-=()

template<typename Fr >

Polynomial< Fr > & barretenberg::Polynomial< Fr >::operator-= ( std::span< const Fr > other )

subtracts the polynomial q(X) 'other'.

Parameters

other q(X)

◆ partial_evaluate_mle()

template<typename Fr >

Polynomial< Fr > barretenberg::Polynomial< Fr >::partial_evaluate_mle ( std::span< const Fr > evaluation_points ) const

Partially evaluates in the last k variables a polynomial interpreted as a multilinear extension.

Partially evaluates p(X) = (a_0, ..., a_{2^n-1}) considered as multilinear extension p(X_0,…,X_{n-1}) = \sum_i a_i*L_i(X_0,…,X_{n-1}) at u = (u_0,…,u_{m-1}), m < n, in the last m variables X_n-m,…,X_{n-1}. The result is a multilinear polynomial in n-m variables g(X_0,…,X_{n-m-1})) = p(X_0,…,X_{n-m-1},u_0,...u_{m-1}).

Note: Intuitively, partially evaluating in one variable collapses the hypercube in one dimension, halving the number of coefficients needed to represent the result. To partially evaluate starting with the first variable (as is done in evaluate_mle), the vector of coefficents is halved by combining adjacent rows in a pairwise fashion (similar to what is done in Sumcheck via "edges"). To evaluate starting from the last variable, we instead bisect the whole vector and combine the two halves. I.e. rather than coefficents being combined with their immediate neighbor, they are combined with the coefficient that lives n/2 indices away.

Parameters

evaluation_points an MLE partial evaluation point u = (u_0,…,u_{m-1})

Returns: Polynomial<Fr> g(X_0,…,X_{n-m-1})) = p(X_0,…,X_{n-m-1},u_0,...u_{m-1})

◆ set_to_right_shifted()

template<typename Fr >

void barretenberg::Polynomial< Fr >::set_to_right_shifted	(	std::span< Fr >	coeffs_in,
		size_t	shift_size = `1`
	)

Set self to the right shift of input coefficients.

Set the size of self to match the input then set coefficients equal to right shift of input. Note: The shifted result is constructed with its first shift-many coefficients equal to zero, so we assert that the last shift-size many input coefficients are equal to zero to ensure that the relationship f(X) = f_{shift}(X)/X^m holds. This is analagous to asserting the first coefficient is 0 in our left-shift-by-one method.

Parameters

coeffs_in
shift_size

◆ share()

template<typename Fr >

Polynomial< Fr > barretenberg::Polynomial< Fr >::share

Return a shallow clone of the polynomial. i.e. underlying memory is shared.

◆ shifted()

template<typename Fr >

Polynomial< Fr > barretenberg::Polynomial< Fr >::shifted

Returns an std::span of the left-shift of self.

If the n coefficients of self are (0, a₁, …, aₙ₋₁), we returns the view of the n-1 coefficients (a₁, …, aₙ₋₁).

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

src/barretenberg/polynomials/polynomial.hpp
src/barretenberg/polynomials/polynomial.cpp

Public Types

Public Member Functions

Member Typedef Documentation

◆ value_type

Constructor & Destructor Documentation

◆ Polynomial() [1/3]

◆ Polynomial() [2/3]

◆ Polynomial() [3/3]

Member Function Documentation

◆ add_scaled()

◆ evaluate_mle()

◆ factor_roots()

◆ fft()

◆ operator*=()

◆ operator+=()

◆ operator-=()

◆ partial_evaluate_mle()

◆ set_to_right_shifted()

◆ share()

◆ shifted()