A univariate polynomial represented by its values on {domain_start, domain_start + 1,..., domain_end - 1}. For memory efficiency purposes, we store the evaluations in an array starting from 0 and make the mapping to the right domain under the hood.
More...
|
| | Univariate ()=default |
| |
| | Univariate (std::array< Fr, LENGTH > evaluations) |
| |
| | ~Univariate ()=default |
| |
| | Univariate (const Univariate &other)=default |
| |
| | Univariate (Univariate &&other) noexcept=default |
| |
| Univariate & | operator= (const Univariate &other)=default |
| |
| Univariate & | operator= (Univariate &&other) noexcept=default |
| |
| | operator UnivariateCoefficientBasis< Fr, 2, true > () const |
| |
| template<bool has_a0_plus_a1> |
| | Univariate (UnivariateCoefficientBasis< Fr, 2, has_a0_plus_a1 > monomial) |
| |
| template<bool has_a0_plus_a1> |
| | Univariate (UnivariateCoefficientBasis< Fr, 3, has_a0_plus_a1 > monomial) |
| |
| Univariate< Fr, domain_end, domain_start > | convert () const noexcept |
| | Convert from a version with skipped evaluations to one without skipping (with zeroes in previously skipped locations)
|
| |
| | Univariate (Fr value) |
| |
| | Univariate (UnivariateView< Fr, domain_end, domain_start, skip_count > in) |
| |
| Fr & | value_at (size_t i) |
| |
| const Fr & | value_at (size_t i) const |
| |
| size_t | size () |
| |
| bool | is_zero () const |
| |
| std::vector< uint8_t > | to_buffer () const |
| |
| bool | operator== (const Univariate &other) const =default |
| |
| Univariate & | operator+= (const Univariate &other) |
| |
| Univariate & | operator-= (const Univariate &other) |
| |
| Univariate & | operator*= (const Univariate &other) |
| |
| Univariate & | self_sqr () |
| |
| Univariate | operator+ (const Univariate &other) const |
| |
| Univariate | operator- (const Univariate &other) const |
| |
| Univariate | operator- () const |
| |
| Univariate | operator* (const Univariate &other) const |
| |
| Univariate | sqr () const |
| |
| Univariate & | operator+= (const Fr &scalar) |
| |
| Univariate & | operator-= (const Fr &scalar) |
| |
| Univariate & | operator*= (const Fr &scalar) |
| |
| Univariate | operator+ (const Fr &scalar) const |
| |
| Univariate | operator- (const Fr &scalar) const |
| |
| Univariate | operator* (const Fr &scalar) const |
| |
| Univariate & | operator+= (const UnivariateView< Fr, domain_end, domain_start, skip_count > &view) |
| |
| Univariate & | operator-= (const UnivariateView< Fr, domain_end, domain_start, skip_count > &view) |
| |
| Univariate & | operator*= (const UnivariateView< Fr, domain_end, domain_start, skip_count > &view) |
| |
| Univariate | operator+ (const UnivariateView< Fr, domain_end, domain_start, skip_count > &view) const |
| |
| Univariate | operator- (const UnivariateView< Fr, domain_end, domain_start, skip_count > &view) const |
| |
| Univariate | operator* (const UnivariateView< Fr, domain_end, domain_start, skip_count > &view) const |
| |
template<size_t EXTENDED_DOMAIN_END, size_t NUM_SKIPPED_INDICES = 0>
requires (domain_start == 0 && domain_end == 2) |
| | operator Univariate< Fr, EXTENDED_DOMAIN_END, 0, NUM_SKIPPED_INDICES > () |
| |
| template<size_t EXTENDED_DOMAIN_END, size_t NUM_SKIPPED_INDICES = 0> |
| Univariate< Fr, EXTENDED_DOMAIN_END, 0, NUM_SKIPPED_INDICES > | extend_to () const |
| | Given a univariate f represented by {f(domain_start), ..., f(domain_end - 1)}, compute the evaluations {f(domain_end),..., f(extended_domain_end -1)} and return the Univariate represented by {f(domain_start),..., f(extended_domain_end -1)}.
|
| |
| template<size_t INITIAL_LENGTH> |
| void | self_extend_from () |
| | Compute the evaluations of the polynomial from the INITIAL_LENGTH up to the total LENGTH. Currently only supports INITIAL_LENGTH = 2.
|
| |
| Fr | evaluate (const Fr &u) const |
| | Evaluate a univariate at a point u not known at compile time and assumed not to be in the domain (else we divide by zero).
|
| |
| auto | begin () |
| |
| auto | begin () const |
| |
| auto | end () |
| |
| auto | end () const |
| |
template<class
Fr, size_t domain_end, size_t domain_start = 0, size_t skip_count = 0>
class bb::Univariate< Fr, domain_end, domain_start, skip_count >
A univariate polynomial represented by its values on {domain_start, domain_start + 1,..., domain_end - 1}. For memory efficiency purposes, we store the evaluations in an array starting from 0 and make the mapping to the right domain under the hood.
- Template Parameters
-
| skip_count | Skip computing the values of the univariate at the points [domain_start+1, .., domain_start+skip_count]. Used for optimising the computation of the combiner (the polynomial \(G\)) in Protogalaxy. The value at [domain_start] is the value from the accumulator, while the values at [domain_start+1, ... domain_start + skip_count] should be zero if the skip_count-many keys to be folded are all valid. |
Definition at line 36 of file univariate.hpp.
template<class
Fr , size_t domain_end, size_t domain_start = 0, size_t skip_count = 0>
template<size_t EXTENDED_DOMAIN_END, size_t NUM_SKIPPED_INDICES = 0>
| Univariate< Fr, EXTENDED_DOMAIN_END, 0, NUM_SKIPPED_INDICES > bb::Univariate< Fr, domain_end, domain_start, skip_count >::extend_to |
( |
| ) |
const |
|
inline |
Given a univariate f represented by {f(domain_start), ..., f(domain_end - 1)}, compute the evaluations {f(domain_end),..., f(extended_domain_end -1)} and return the Univariate represented by {f(domain_start),..., f(extended_domain_end -1)}.
Write v_i = f(x_i) on a the domain {x_{domain_start}, ..., x_{domain_end-1}}. To efficiently compute the needed values of f, we use the barycentric formula
- f(x) = B(x) Σ_{i=domain_start}^{domain_end-1} v_i / (d_i*(x-x_i)) where
- B(x) = Π_{i=domain_start}^{domain_end-1} (x-x_i)
- d_i = Π_{j ∈ {domain_start, ..., domain_end-1}, j≠i} (x_i-x_j) for i ∈ {domain_start, ..., domain_end-1}
When the domain size is two, extending f = v0(1-X) + v1X to a new value involves just one addition and a subtraction: setting Δ = v1-v0, the values of f(X) are f(0)=v0, f(1)= v0 + Δ, v2 = f(1) + Δ, v3 = f(2) + Δ...
Definition at line 440 of file univariate.hpp.
1.9.8