evaluations.rs
1 // Copyright (c) 2025 ADnet Contributors 2 // This file is part of the AlphaVM library. 3 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at: 7 8 // http://www.apache.org/licenses/LICENSE-2.0 9 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 16 //! A polynomial represented in evaluations form. 17 18 use crate::fft::{DensePolynomial, EvaluationDomain}; 19 #[cfg(feature = "serial")] 20 use itertools::Itertools; 21 #[cfg(not(feature = "serial"))] 22 use rayon::prelude::*; 23 24 use alphavm_fields::PrimeField; 25 use alphavm_utilities::{cfg_iter, cfg_iter_mut, serialize::*}; 26 27 use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign}; 28 29 use super::domain::IFFTPrecomputation; 30 31 /// Stores a polynomial in evaluation form. 32 #[derive(Clone, PartialEq, Eq, Hash, Debug, CanonicalSerialize, CanonicalDeserialize)] 33 pub struct Evaluations<F: PrimeField> { 34 /// The evaluations of a polynomial over the domain `D` 35 pub evaluations: Vec<F>, 36 #[doc(hidden)] 37 domain: EvaluationDomain<F>, 38 } 39 40 impl<F: PrimeField> Evaluations<F> { 41 /// Construct `Self` from evaluations and a domain. 42 pub fn from_vec_and_domain(mut evaluations: Vec<F>, domain: EvaluationDomain<F>) -> Self { 43 // Pad evaluations to ensure we can always evaluate 44 evaluations.resize(domain.size(), F::zero()); 45 Self { evaluations, domain } 46 } 47 48 /// Interpolate a polynomial from a list of evaluations 49 pub fn interpolate_by_ref(&self) -> DensePolynomial<F> { 50 DensePolynomial::from_coefficients_vec(self.domain.ifft(&self.evaluations)) 51 } 52 53 /// Interpolate a polynomial from a list of evaluations 54 pub fn interpolate_with_pc_by_ref(&self, pc: &IFFTPrecomputation<F>) -> DensePolynomial<F> { 55 let mut evals = self.evaluations.clone(); 56 evals.resize(self.domain.size(), F::zero()); 57 self.domain.in_order_ifft_in_place_with_pc(&mut evals, pc); 58 DensePolynomial::from_coefficients_vec(evals) 59 } 60 61 /// Interpolate a polynomial from a list of evaluations 62 pub fn interpolate(self) -> DensePolynomial<F> { 63 let Self { evaluations: mut evals, domain } = self; 64 domain.ifft_in_place(&mut evals); 65 DensePolynomial::from_coefficients_vec(evals) 66 } 67 68 /// Interpolate a polynomial from a list of evaluations 69 pub fn interpolate_with_pc(self, pc: &IFFTPrecomputation<F>) -> DensePolynomial<F> { 70 let Self { evaluations: mut evals, domain } = self; 71 evals.resize(self.domain.size(), F::zero()); 72 domain.in_order_ifft_in_place_with_pc(&mut evals, pc); 73 DensePolynomial::from_coefficients_vec(evals) 74 } 75 76 /// Returns the evaluations of `self`. 77 pub fn evaluations(&self) -> &[F] { 78 &self.evaluations 79 } 80 81 pub fn domain(&self) -> EvaluationDomain<F> { 82 self.domain 83 } 84 85 pub fn evaluate(&self, point: &F) -> F { 86 let coeffs = self.domain.evaluate_all_lagrange_coefficients(*point); 87 self.evaluate_with_coeffs(&coeffs) 88 } 89 90 pub fn evaluate_with_coeffs(&self, lagrange_coefficients_at_point: &[F]) -> F { 91 cfg_iter!(self.evaluations).zip_eq(lagrange_coefficients_at_point).map(|(a, b)| *a * b).sum() 92 } 93 } 94 95 impl<F: PrimeField> std::ops::Index<usize> for Evaluations<F> { 96 type Output = F; 97 98 fn index(&self, index: usize) -> &F { 99 &self.evaluations[index] 100 } 101 } 102 103 impl<'a, F: PrimeField> Mul<&'a Evaluations<F>> for &'_ Evaluations<F> { 104 type Output = Evaluations<F>; 105 106 #[inline] 107 fn mul(self, other: &'a Evaluations<F>) -> Evaluations<F> { 108 let mut result = self.clone(); 109 result *= other; 110 result 111 } 112 } 113 114 impl<'a, F: PrimeField> MulAssign<&'a Evaluations<F>> for Evaluations<F> { 115 #[inline] 116 fn mul_assign(&mut self, other: &'a Evaluations<F>) { 117 assert_eq!(self.domain, other.domain, "domains are unequal"); 118 cfg_iter_mut!(self.evaluations).zip_eq(&other.evaluations).for_each(|(a, b)| *a *= b); 119 } 120 } 121 122 impl<'a, F: PrimeField> Add<&'a Evaluations<F>> for &'_ Evaluations<F> { 123 type Output = Evaluations<F>; 124 125 #[inline] 126 fn add(self, other: &'a Evaluations<F>) -> Evaluations<F> { 127 let mut result = self.clone(); 128 result += other; 129 result 130 } 131 } 132 133 impl<'a, F: PrimeField> AddAssign<&'a Evaluations<F>> for Evaluations<F> { 134 #[inline] 135 fn add_assign(&mut self, other: &'a Evaluations<F>) { 136 assert_eq!(self.domain, other.domain, "domains are unequal"); 137 cfg_iter_mut!(self.evaluations).zip_eq(&other.evaluations).for_each(|(a, b)| *a += b); 138 } 139 } 140 141 impl<'a, F: PrimeField> Sub<&'a Evaluations<F>> for &'_ Evaluations<F> { 142 type Output = Evaluations<F>; 143 144 #[inline] 145 fn sub(self, other: &'a Evaluations<F>) -> Evaluations<F> { 146 let mut result = self.clone(); 147 result -= other; 148 result 149 } 150 } 151 152 impl<'a, F: PrimeField> SubAssign<&'a Evaluations<F>> for Evaluations<F> { 153 #[inline] 154 fn sub_assign(&mut self, other: &'a Evaluations<F>) { 155 assert_eq!(self.domain, other.domain, "domains are unequal"); 156 cfg_iter_mut!(self.evaluations).zip_eq(&other.evaluations).for_each(|(a, b)| *a -= b); 157 } 158 } 159 160 impl<'a, F: PrimeField> Div<&'a Evaluations<F>> for &'_ Evaluations<F> { 161 type Output = Evaluations<F>; 162 163 #[inline] 164 fn div(self, other: &'a Evaluations<F>) -> Evaluations<F> { 165 let mut result = self.clone(); 166 result /= other; 167 result 168 } 169 } 170 171 impl<'a, F: PrimeField> DivAssign<&'a Evaluations<F>> for Evaluations<F> { 172 #[inline] 173 fn div_assign(&mut self, other: &'a Evaluations<F>) { 174 assert_eq!(self.domain, other.domain, "domains are unequal"); 175 cfg_iter_mut!(self.evaluations).zip_eq(&other.evaluations).for_each(|(a, b)| *a /= b); 176 } 177 }