zinc_poly/univariate/dynamic/
over_fixed_semiring.rs

1use crypto_primitives::{
2    FixedSemiring, FromWithConfig, IntoWithConfig, PrimeField, Ring, Semiring, boolean::Boolean,
3};
4use derive_more::From;
5use num_traits::{CheckedAdd, CheckedMul, CheckedNeg, CheckedSub, ConstZero, One, Zero};
6use std::{
7    fmt::Display,
8    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
9};
10use zinc_utils::{
11    CHECKED, UNCHECKED, mul_by_scalar::MulByScalar, projectable_to_field::ProjectableToField,
12};
13
14use crate::{
15    EvaluatablePolynomial, EvaluationError, Polynomial,
16    univariate::{
17        binary::BinaryPoly,
18        dense::DensePolynomial,
19        dynamic::{self, over_field::DynamicPolynomialF},
20    },
21};
22
23/// Polynomials of dynamic degree. The implementation
24/// is tailored to work with `FixedSemiring`s. To be used
25/// in UAIR and PIOP where ZIP+ degree bound
26/// is not observed anymore.
27///
28/// Note that operations involving dynamic polynomials
29/// do not trim leading zeros meaning
30/// one can end up with unequal objects of the type
31/// `DynamicPoly<R>` that represent equal polynomials,
32/// therefore `trim` has to be called before checking
33/// equality.
34#[derive(Debug, Default, Clone, From, Hash, PartialEq, Eq)]
35pub struct DynamicPolynomialFS<R: FixedSemiring> {
36    pub coeffs: Vec<R>,
37}
38
39impl<R: FixedSemiring> DynamicPolynomialFS<R> {
40    /// Create a new polynomial with the given coefficients.
41    #[inline(always)]
42    pub fn new_trimmed(coeffs: impl AsRef<[R]>) -> Self {
43        Self {
44            coeffs: dynamic::new_coeffs_trimmed(coeffs.as_ref(), R::is_zero),
45        }
46    }
47
48    #[inline(always)]
49    pub fn new(coeffs: impl AsRef<[R]>) -> Self {
50        Self {
51            coeffs: Vec::from(coeffs.as_ref()),
52        }
53    }
54
55    #[inline(always)]
56    pub fn degree(&self) -> Option<usize> {
57        dynamic::degree(&self.coeffs, R::is_zero)
58    }
59
60    #[inline(always)]
61    pub fn trim(&mut self) {
62        dynamic::trim(&mut self.coeffs, R::is_zero);
63    }
64}
65
66impl<R: FixedSemiring> Display for DynamicPolynomialFS<R> {
67    #[inline(always)]
68    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
69        dynamic::display(&self.coeffs, f)
70    }
71}
72
73impl<R: FixedSemiring> Zero for DynamicPolynomialFS<R> {
74    #[inline(always)]
75    fn zero() -> Self {
76        Default::default()
77    }
78
79    #[inline(always)]
80    fn is_zero(&self) -> bool {
81        dynamic::is_zero(&self.coeffs, R::is_zero)
82    }
83}
84
85impl<R: FixedSemiring> ConstZero for DynamicPolynomialFS<R> {
86    const ZERO: Self = Self { coeffs: Vec::new() };
87}
88
89impl<R: FixedSemiring> One for DynamicPolynomialFS<R> {
90    fn one() -> Self {
91        Self {
92            coeffs: vec![R::one()],
93        }
94    }
95}
96
97impl<R: FixedSemiring + Ring> Neg for DynamicPolynomialFS<R> {
98    type Output = Self;
99
100    fn neg(self) -> Self::Output {
101        Self {
102            coeffs: dynamic::neg(self.coeffs),
103        }
104    }
105}
106
107impl<R: FixedSemiring> Add for DynamicPolynomialFS<R> {
108    type Output = Self;
109
110    fn add(self, rhs: Self) -> Self::Output {
111        self.add(&rhs)
112    }
113}
114
115impl<R: FixedSemiring> Add<&Self> for DynamicPolynomialFS<R> {
116    type Output = Self;
117
118    fn add(mut self, rhs: &Self) -> Self::Output {
119        self.add_assign(rhs);
120
121        self
122    }
123}
124
125impl<R: FixedSemiring> Sub for DynamicPolynomialFS<R> {
126    type Output = Self;
127
128    fn sub(self, rhs: Self) -> Self::Output {
129        self.sub(&rhs)
130    }
131}
132
133impl<R: FixedSemiring> Sub<&Self> for DynamicPolynomialFS<R> {
134    type Output = Self;
135
136    fn sub(mut self, rhs: &Self) -> Self::Output {
137        self.sub_assign(rhs);
138
139        self
140    }
141}
142
143impl<R: FixedSemiring> Mul for DynamicPolynomialFS<R> {
144    type Output = Self;
145
146    #[allow(clippy::arithmetic_side_effects)]
147    fn mul(self, rhs: Self) -> Self::Output {
148        &self * &rhs
149    }
150}
151
152impl<R: FixedSemiring> Mul<&Self> for DynamicPolynomialFS<R> {
153    type Output = Self;
154
155    #[allow(clippy::arithmetic_side_effects)]
156    fn mul(self, rhs: &Self) -> Self::Output {
157        &self * rhs
158    }
159}
160
161impl<'a, R: FixedSemiring> Mul<&'a DynamicPolynomialFS<R>> for &'a DynamicPolynomialFS<R> {
162    type Output = DynamicPolynomialFS<R>;
163
164    fn mul(self, rhs: Self) -> Self::Output {
165        Self::Output {
166            coeffs: dynamic::mul::<_, UNCHECKED>(&self.coeffs, &rhs.coeffs, R::is_zero)
167                .expect("we do not expect overflow here"),
168        }
169    }
170}
171
172impl<R: FixedSemiring> CheckedAdd for DynamicPolynomialFS<R> {
173    fn checked_add(&self, rhs: &Self) -> Option<Self> {
174        let mut res = self.clone();
175
176        if self.coeffs.len() < rhs.coeffs.len() {
177            res.coeffs.resize(rhs.coeffs.len(), R::zero());
178        }
179
180        res.coeffs
181            .iter_mut()
182            .zip(rhs.coeffs.iter())
183            .try_for_each(|(lhs, rhs)| {
184                *lhs = lhs.checked_add(rhs)?;
185                Some(())
186            })?;
187
188        Some(res)
189    }
190}
191
192impl<R: FixedSemiring> CheckedSub for DynamicPolynomialFS<R> {
193    fn checked_sub(&self, rhs: &Self) -> Option<Self> {
194        let mut res = self.clone();
195
196        if self.coeffs.len() < rhs.coeffs.len() {
197            res.coeffs.resize(rhs.coeffs.len(), R::zero());
198        }
199
200        res.coeffs
201            .iter_mut()
202            .zip(rhs.coeffs.iter())
203            .try_for_each(|(lhs, rhs)| {
204                *lhs = lhs.checked_sub(rhs)?;
205                Some(())
206            })?;
207
208        Some(res)
209    }
210}
211
212impl<R: FixedSemiring> CheckedMul for DynamicPolynomialFS<R> {
213    #[allow(clippy::arithmetic_side_effects)] // degrees normally shouldn't be that large
214    fn checked_mul(&self, rhs: &Self) -> Option<Self> {
215        Some(Self {
216            coeffs: dynamic::mul::<_, CHECKED>(&self.coeffs, &rhs.coeffs, R::is_zero)?,
217        })
218    }
219}
220
221impl<R: FixedSemiring + Ring> CheckedNeg for DynamicPolynomialFS<R> {
222    fn checked_neg(&self) -> Option<Self> {
223        Some(Self {
224            coeffs: self
225                .coeffs
226                .iter()
227                .map(|coeff| coeff.checked_neg())
228                .collect::<Option<Vec<_>>>()?,
229        })
230    }
231}
232
233impl<R: FixedSemiring> AddAssign for DynamicPolynomialFS<R> {
234    fn add_assign(&mut self, rhs: Self) {
235        self.add_assign(&rhs);
236    }
237}
238
239impl<R: FixedSemiring> AddAssign<&Self> for DynamicPolynomialFS<R> {
240    fn add_assign(&mut self, rhs: &Self) {
241        dynamic::add_assign(&mut self.coeffs, &rhs.coeffs, |_| R::zero());
242    }
243}
244
245impl<R: FixedSemiring> SubAssign for DynamicPolynomialFS<R> {
246    #[allow(clippy::arithmetic_side_effects)] // by definition
247    fn sub_assign(&mut self, rhs: Self) {
248        self.sub_assign(&rhs);
249    }
250}
251
252impl<R: FixedSemiring> SubAssign<&Self> for DynamicPolynomialFS<R> {
253    #[allow(clippy::arithmetic_side_effects)] // by definition
254    fn sub_assign(&mut self, rhs: &Self) {
255        dynamic::sub_assign(&mut self.coeffs, &rhs.coeffs, |_| R::zero());
256    }
257}
258
259impl<R: FixedSemiring> MulAssign for DynamicPolynomialFS<R> {
260    #[allow(clippy::arithmetic_side_effects)] // by definition
261    fn mul_assign(&mut self, rhs: Self) {
262        let res = rhs * &*self;
263
264        *self = res
265    }
266}
267
268impl<R: FixedSemiring> MulAssign<&Self> for DynamicPolynomialFS<R> {
269    #[allow(clippy::arithmetic_side_effects)] // by definition
270    fn mul_assign(&mut self, rhs: &Self) {
271        let res = &*self * rhs;
272
273        *self = res;
274    }
275}
276
277impl<R: FixedSemiring> Semiring for DynamicPolynomialFS<R> {}
278impl<R: FixedSemiring + Ring> Ring for DynamicPolynomialFS<R> {}
279
280impl<R: FixedSemiring, const DEGREE_PLUS_ONE: usize> From<DensePolynomial<R, DEGREE_PLUS_ONE>>
281    for DynamicPolynomialFS<R>
282{
283    fn from(dense_poly: DensePolynomial<R, DEGREE_PLUS_ONE>) -> Self {
284        Self {
285            coeffs: Vec::from(dense_poly.coeffs),
286        }
287    }
288}
289
290impl<const DEGREE_PLUS_ONE: usize> From<BinaryPoly<DEGREE_PLUS_ONE>>
291    for DynamicPolynomialFS<Boolean>
292{
293    fn from(binary_poly: BinaryPoly<DEGREE_PLUS_ONE>) -> Self {
294        Self::from(DensePolynomial::from(binary_poly))
295    }
296}
297
298impl<R: FixedSemiring> Polynomial<R> for DynamicPolynomialFS<R> {
299    const DEGREE_BOUND: usize = usize::MAX;
300}
301
302impl<R: FixedSemiring> EvaluatablePolynomial<R, R> for DynamicPolynomialFS<R> {
303    type EvaluationPoint = R;
304
305    fn evaluate_at_point(&self, point: &R) -> Result<R, EvaluationError> {
306        // Horner's method.
307        let mut result = self
308            .coeffs
309            .last()
310            .ok_or(EvaluationError::EmptyPolynomial)?
311            .clone();
312
313        for coeff in self.coeffs.iter().rev().skip(1) {
314            let term = result.checked_mul(point).ok_or(EvaluationError::Overflow)?;
315            result = term.checked_add(coeff).ok_or(EvaluationError::Overflow)?;
316        }
317
318        Ok(result)
319    }
320}
321
322impl<R, F> ProjectableToField<F> for DynamicPolynomialFS<R>
323where
324    R: FixedSemiring,
325    F: PrimeField + for<'a> FromWithConfig<&'a R> + for<'a> MulByScalar<&'a F> + 'static,
326{
327    #![allow(clippy::arithmetic_side_effects)] // False alert, field operations are safe
328    fn prepare_projection(
329        sampled_value: &F,
330    ) -> impl Fn(&DynamicPolynomialFS<R>) -> F + Send + Sync + 'static {
331        let sampled_value = sampled_value.clone();
332        let field_cfg = sampled_value.cfg().clone();
333
334        move |poly: &DynamicPolynomialFS<R>| {
335            let coeffs: Vec<F> = poly
336                .coeffs
337                .iter()
338                .map(|v| v.into_with_cfg(&field_cfg))
339                .collect();
340
341            let poly2 = DynamicPolynomialF { coeffs };
342            poly2
343                .evaluate_at_point(&sampled_value)
344                .expect("Failed to evaluate polynomial at point")
345        }
346    }
347}
348
349#[cfg(test)]
350mod tests {
351    use crypto_primitives::crypto_bigint_int::Int;
352
353    use super::*;
354
355    #[test]
356    fn new_creates_correctly() {
357        assert_eq!(
358            DynamicPolynomialFS::new_trimmed([1i32, 2i32, 3i32, 0, 0]),
359            DynamicPolynomialFS {
360                coeffs: vec![1, 2, 3]
361            }
362        );
363    }
364
365    fn get_2_test_polynomial() -> (DynamicPolynomialFS<Int<4>>, DynamicPolynomialFS<Int<4>>) {
366        let x = DynamicPolynomialFS::new(vec![
367            Int::from_i8(2),
368            Int::from_i8(0),
369            Int::from_i8(2),
370            Int::from_i8(0),
371            Int::from_i8(0),
372        ]);
373
374        let y = DynamicPolynomialFS::new(vec![Int::from_i8(1), Int::from_i8(2), Int::from_i8(3)]);
375
376        (x, y)
377    }
378
379    #[test]
380    fn add_zero() {
381        assert_eq!(
382            DynamicPolynomialFS::<Int<4>>::ZERO + DynamicPolynomialFS::ZERO,
383            DynamicPolynomialFS::ZERO
384        );
385
386        let x = DynamicPolynomialFS::new(vec![
387            Int::<4>::from_i8(2),
388            Int::from_i8(0),
389            Int::from_i8(2),
390            Int::from_i8(0),
391            Int::from_i8(0),
392        ]);
393
394        assert_eq!(x.clone() + &DynamicPolynomialFS::ZERO, x);
395        assert_eq!(DynamicPolynomialFS::ZERO + x.clone(), x);
396        assert_eq!(DynamicPolynomialFS::ZERO + &x, x);
397
398        let mut y = x.clone();
399
400        y += DynamicPolynomialFS::ZERO;
401
402        assert_eq!(y, x);
403
404        y += &DynamicPolynomialFS::ZERO;
405
406        assert_eq!(y, x);
407    }
408
409    #[test]
410    fn addition_is_correct() {
411        let (x, y) = get_2_test_polynomial();
412
413        let res = DynamicPolynomialFS::new(vec![
414            Int::<4>::from_i8(3),
415            Int::from_i8(2),
416            Int::from_i8(5),
417            Int::ZERO,
418            Int::ZERO,
419        ]);
420
421        assert_eq!(x.clone() + &y, res);
422        assert_eq!(y.clone() + &x, res);
423        assert_eq!(x.clone() + y.clone(), res);
424        assert_eq!(x.checked_add(&y), Some(res.clone()));
425
426        let mut z = x.clone();
427        z += y.clone();
428        assert_eq!(z, res);
429
430        let mut z = x.clone();
431        z += &y;
432        assert_eq!(z, res);
433
434        let mut z = y.clone();
435        z += x.clone();
436        assert_eq!(z, res);
437
438        let mut z = y.clone();
439        z += &x;
440        assert_eq!(z, res);
441    }
442
443    #[test]
444    fn subtraction_is_correct() {
445        let (x, y) = get_2_test_polynomial();
446
447        let res = DynamicPolynomialFS::new(vec![
448            Int::<4>::from_i8(1),
449            Int::from_i8(-2),
450            Int::from_i8(-1),
451            Int::ZERO,
452            Int::ZERO,
453        ]);
454
455        assert_eq!(x.clone() - &y, res);
456        assert_eq!(x.clone() - y.clone(), res);
457        assert_eq!(x.checked_sub(&y), Some(res.clone()));
458
459        let mut z = x.clone();
460        z -= y.clone();
461        assert_eq!(z, res);
462
463        let mut z = x.clone();
464        z -= &y;
465        assert_eq!(z, res);
466
467        let x = y;
468        let y = DynamicPolynomialFS::new(vec![
469            Int::from_i8(2),
470            Int::from_i8(0),
471            Int::from_i8(2),
472            Int::from_i8(-1),
473            Int::ZERO,
474        ]);
475
476        let res = DynamicPolynomialFS::new(vec![
477            Int::<4>::from_i8(-1),
478            Int::from_i8(2),
479            Int::from_i8(1),
480            Int::from_i8(1),
481            Int::ZERO,
482        ]);
483
484        assert_eq!(x.clone() - &y, res);
485        assert_eq!(x.clone() - y.clone(), res);
486        assert_eq!(x.checked_sub(&y), Some(res.clone()));
487
488        let mut z = x.clone();
489        z -= y.clone();
490        assert_eq!(z, res);
491
492        let mut z = x.clone();
493        z -= &y;
494        assert_eq!(z, res);
495    }
496
497    #[test]
498    fn mul_zero() {
499        assert_eq!(
500            DynamicPolynomialFS::<Int<4>>::ZERO * DynamicPolynomialFS::ZERO,
501            DynamicPolynomialFS::ZERO
502        );
503
504        let x = DynamicPolynomialFS::new(vec![
505            Int::<4>::from_i8(2),
506            Int::from_i8(0),
507            Int::from_i8(2),
508            Int::from_i8(0),
509            Int::from_i8(0),
510        ]);
511
512        assert_eq!(
513            x.clone() * &DynamicPolynomialFS::ZERO,
514            DynamicPolynomialFS::ZERO
515        );
516        assert_eq!(
517            DynamicPolynomialFS::ZERO * x.clone(),
518            DynamicPolynomialFS::ZERO
519        );
520        assert_eq!(DynamicPolynomialFS::ZERO * &x, DynamicPolynomialFS::ZERO);
521
522        let mut y = x.clone();
523
524        y *= DynamicPolynomialFS::ZERO;
525
526        assert_eq!(y, DynamicPolynomialFS::ZERO);
527
528        y *= &DynamicPolynomialFS::ZERO;
529
530        assert_eq!(y, DynamicPolynomialFS::ZERO);
531    }
532
533    #[test]
534    fn multiplication_is_correct() {
535        let (x, y) = get_2_test_polynomial();
536
537        let res = DynamicPolynomialFS::new(vec![
538            Int::<4>::from_i8(2),
539            Int::from_i8(4),
540            Int::from_i8(8),
541            Int::from_i8(4),
542            Int::from_i8(6),
543            Int::ZERO,
544            Int::ZERO,
545        ]);
546
547        assert_eq!(x.clone() * y.clone(), res);
548        assert_eq!(x.clone() * &y, res);
549        assert_eq!(&x * &y, res);
550        assert_eq!(y.clone() * x.clone(), res);
551        assert_eq!(y.clone() * &x, res);
552        assert_eq!(&y * &x, res);
553        assert_eq!(x.checked_mul(&y), Some(res.clone()));
554        assert_eq!(y.checked_mul(&x), Some(res.clone()));
555
556        let mut z = x.clone();
557        z *= y.clone();
558        assert_eq!(z, res);
559
560        let mut z = x.clone();
561        z *= &y;
562        assert_eq!(z, res);
563
564        let mut z = y.clone();
565        z *= x.clone();
566        assert_eq!(z, res);
567
568        let mut z = y.clone();
569        z *= &x;
570        assert_eq!(z, res);
571    }
572
573    #[test]
574    fn test_trim() {
575        let mut x = DynamicPolynomialFS::<Int<4>>::new([
576            Int::ZERO,
577            Int::ZERO,
578            Int::ZERO,
579            Int::ZERO,
580            Int::ZERO,
581        ]);
582        x.trim();
583        assert_eq!(x, DynamicPolynomialFS::ZERO);
584
585        let mut x = DynamicPolynomialFS::<Int<4>>::new([
586            Int::from_i8(2),
587            Int::from_i8(3),
588            Int::ZERO,
589            Int::ZERO,
590            Int::ZERO,
591        ]);
592        x.trim();
593        assert_eq!(
594            x,
595            DynamicPolynomialFS::<Int<4>>::new([Int::from_i8(2), Int::from_i8(3),])
596        );
597    }
598}
zinc_poly/univariate/dynamic/over_fixed_semiring.rs

zinc_poly/univariate/dynamic/
over_fixed_semiring.rs
