evaluations.rs
1 // Copyright (c) 2025-2026 ACDC Network 2 // This file is part of the alphavm library. 3 // 4 // Alpha Chain | Delta Chain Protocol 5 // International Monetary Graphite. 6 // 7 // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com). 8 // They built world-class ZK infrastructure. We installed the EASY button. 9 // Their cryptography: elegant. Our modifications: bureaucracy-compatible. 10 // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours. 11 // 12 // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0 13 // All modifications and new work: CC0 1.0 Universal Public Domain Dedication. 14 // No rights reserved. No permission required. No warranty. No refunds. 15 // 16 // https://creativecommons.org/publicdomain/zero/1.0/ 17 // SPDX-License-Identifier: CC0-1.0 18 19 //! A polynomial represented in evaluations form. 20 21 use crate::fft::{DensePolynomial, EvaluationDomain}; 22 #[cfg(feature = "serial")] 23 use itertools::Itertools; 24 #[cfg(not(feature = "serial"))] 25 use rayon::prelude::*; 26 27 use alphavm_fields::PrimeField; 28 use alphavm_utilities::{cfg_iter, cfg_iter_mut, serialize::*}; 29 30 use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign}; 31 32 use super::domain::IFFTPrecomputation; 33 34 /// Stores a polynomial in evaluation form. 35 #[derive(Clone, PartialEq, Eq, Hash, Debug, CanonicalSerialize, CanonicalDeserialize)] 36 pub struct Evaluations<F: PrimeField> { 37 /// The evaluations of a polynomial over the domain `D` 38 pub evaluations: Vec<F>, 39 #[doc(hidden)] 40 domain: EvaluationDomain<F>, 41 } 42 43 impl<F: PrimeField> Evaluations<F> { 44 /// Construct `Self` from evaluations and a domain. 45 pub fn from_vec_and_domain(mut evaluations: Vec<F>, domain: EvaluationDomain<F>) -> Self { 46 // Pad evaluations to ensure we can always evaluate 47 evaluations.resize(domain.size(), F::zero()); 48 Self { evaluations, domain } 49 } 50 51 /// Interpolate a polynomial from a list of evaluations 52 pub fn interpolate_by_ref(&self) -> DensePolynomial<F> { 53 DensePolynomial::from_coefficients_vec(self.domain.ifft(&self.evaluations)) 54 } 55 56 /// Interpolate a polynomial from a list of evaluations 57 pub fn interpolate_with_pc_by_ref(&self, pc: &IFFTPrecomputation<F>) -> DensePolynomial<F> { 58 let mut evals = self.evaluations.clone(); 59 evals.resize(self.domain.size(), F::zero()); 60 self.domain.in_order_ifft_in_place_with_pc(&mut evals, pc); 61 DensePolynomial::from_coefficients_vec(evals) 62 } 63 64 /// Interpolate a polynomial from a list of evaluations 65 pub fn interpolate(self) -> DensePolynomial<F> { 66 let Self { evaluations: mut evals, domain } = self; 67 domain.ifft_in_place(&mut evals); 68 DensePolynomial::from_coefficients_vec(evals) 69 } 70 71 /// Interpolate a polynomial from a list of evaluations 72 pub fn interpolate_with_pc(self, pc: &IFFTPrecomputation<F>) -> DensePolynomial<F> { 73 let Self { evaluations: mut evals, domain } = self; 74 evals.resize(self.domain.size(), F::zero()); 75 domain.in_order_ifft_in_place_with_pc(&mut evals, pc); 76 DensePolynomial::from_coefficients_vec(evals) 77 } 78 79 /// Returns the evaluations of `self`. 80 pub fn evaluations(&self) -> &[F] { 81 &self.evaluations 82 } 83 84 pub fn domain(&self) -> EvaluationDomain<F> { 85 self.domain 86 } 87 88 pub fn evaluate(&self, point: &F) -> F { 89 let coeffs = self.domain.evaluate_all_lagrange_coefficients(*point); 90 self.evaluate_with_coeffs(&coeffs) 91 } 92 93 pub fn evaluate_with_coeffs(&self, lagrange_coefficients_at_point: &[F]) -> F { 94 cfg_iter!(self.evaluations).zip_eq(lagrange_coefficients_at_point).map(|(a, b)| *a * b).sum() 95 } 96 } 97 98 impl<F: PrimeField> std::ops::Index<usize> for Evaluations<F> { 99 type Output = F; 100 101 fn index(&self, index: usize) -> &F { 102 &self.evaluations[index] 103 } 104 } 105 106 impl<'a, F: PrimeField> Mul<&'a Evaluations<F>> for &'_ Evaluations<F> { 107 type Output = Evaluations<F>; 108 109 #[inline] 110 fn mul(self, other: &'a Evaluations<F>) -> Evaluations<F> { 111 let mut result = self.clone(); 112 result *= other; 113 result 114 } 115 } 116 117 impl<'a, F: PrimeField> MulAssign<&'a Evaluations<F>> for Evaluations<F> { 118 #[inline] 119 fn mul_assign(&mut self, other: &'a Evaluations<F>) { 120 assert_eq!(self.domain, other.domain, "domains are unequal"); 121 cfg_iter_mut!(self.evaluations).zip_eq(&other.evaluations).for_each(|(a, b)| *a *= b); 122 } 123 } 124 125 impl<'a, F: PrimeField> Add<&'a Evaluations<F>> for &'_ Evaluations<F> { 126 type Output = Evaluations<F>; 127 128 #[inline] 129 fn add(self, other: &'a Evaluations<F>) -> Evaluations<F> { 130 let mut result = self.clone(); 131 result += other; 132 result 133 } 134 } 135 136 impl<'a, F: PrimeField> AddAssign<&'a Evaluations<F>> for Evaluations<F> { 137 #[inline] 138 fn add_assign(&mut self, other: &'a Evaluations<F>) { 139 assert_eq!(self.domain, other.domain, "domains are unequal"); 140 cfg_iter_mut!(self.evaluations).zip_eq(&other.evaluations).for_each(|(a, b)| *a += b); 141 } 142 } 143 144 impl<'a, F: PrimeField> Sub<&'a Evaluations<F>> for &'_ Evaluations<F> { 145 type Output = Evaluations<F>; 146 147 #[inline] 148 fn sub(self, other: &'a Evaluations<F>) -> Evaluations<F> { 149 let mut result = self.clone(); 150 result -= other; 151 result 152 } 153 } 154 155 impl<'a, F: PrimeField> SubAssign<&'a Evaluations<F>> for Evaluations<F> { 156 #[inline] 157 fn sub_assign(&mut self, other: &'a Evaluations<F>) { 158 assert_eq!(self.domain, other.domain, "domains are unequal"); 159 cfg_iter_mut!(self.evaluations).zip_eq(&other.evaluations).for_each(|(a, b)| *a -= b); 160 } 161 } 162 163 impl<'a, F: PrimeField> Div<&'a Evaluations<F>> for &'_ Evaluations<F> { 164 type Output = Evaluations<F>; 165 166 #[inline] 167 fn div(self, other: &'a Evaluations<F>) -> Evaluations<F> { 168 let mut result = self.clone(); 169 result /= other; 170 result 171 } 172 } 173 174 impl<'a, F: PrimeField> DivAssign<&'a Evaluations<F>> for Evaluations<F> { 175 #[inline] 176 fn div_assign(&mut self, other: &'a Evaluations<F>) { 177 assert_eq!(self.domain, other.domain, "domains are unequal"); 178 cfg_iter_mut!(self.evaluations).zip_eq(&other.evaluations).for_each(|(a, b)| *a /= b); 179 } 180 }