zinc_poly/mle/
dense.rs

1mod try_collect_dense_mle;
2
3use crate::{
4    EvaluationError,
5    mle::{MultilinearExtension, MultilinearExtensionRand},
6};
7use core::ops::{Add, AddAssign, Index, IndexMut, Mul, MulAssign, Neg, Sub, SubAssign};
8use crypto_primitives::{FieldConfig, Matrix, Ring, Semiring, SemiringConfig, SetElement};
9use rand::{distr::StandardUniform, prelude::*};
10#[cfg(feature = "parallel")]
11use rayon::prelude::*;
12use std::{
13    fmt::Debug,
14    ops::{Deref, DerefMut},
15    slice::SliceIndex,
16};
17use zinc_utils::{cfg_into_iter, projectable_to_field::ProjectableToField, sub};
18
19pub use try_collect_dense_mle::*;
20
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct DenseMultilinearExtension<T> {
23    /// The evaluation over {0,1}^`num_vars`
24    pub evaluations: Vec<T>,
25    /// Number of variables
26    pub num_vars: usize,
27}
28
29impl<R> DenseMultilinearExtension<R> {
30    pub fn zero_vars(evaluation: R) -> Self {
31        Self {
32            evaluations: vec![evaluation],
33            num_vars: 0,
34        }
35    }
36}
37
38impl<R: Clone> DenseMultilinearExtension<R> {
39    pub fn from_evaluations_slice(num_vars: usize, evaluations: &[R], zero: R) -> Self {
40        Self::from_evaluations_vec(num_vars, evaluations.to_vec(), zero)
41    }
42
43    pub fn from_evaluations_vec(num_vars: usize, evaluations: Vec<R>, zero: R) -> Self {
44        // assert that the number of variables matches the size of evaluations
45        assert!(
46            evaluations.len() <= 1 << num_vars,
47            "The size of evaluations should not exceed 2^num_vars. \n eval len: {:?}. num vars: {num_vars}",
48            evaluations.len()
49        );
50
51        if evaluations.len() != 1 << num_vars {
52            let mut evaluations = evaluations;
53            evaluations.resize(1 << num_vars, zero);
54            return Self {
55                num_vars,
56                evaluations,
57            };
58        }
59
60        Self {
61            num_vars,
62            evaluations,
63        }
64    }
65
66    /// Returns the dense MLE from the given matrix, without modifying the
67    /// original matrix.
68    #[allow(clippy::arithmetic_side_effects)]
69    pub fn from_matrix<M: Matrix<R>>(matrix: &M, zero: R) -> Self {
70        let n_vars: usize = // n_vars = s + s'
71            (zinc_utils::log2(matrix.num_rows()) + zinc_utils::log2(matrix.num_cols())) as usize;
72
73        // Matrices might need to get padded before turned into an MLE
74        let padded_rows = matrix.num_rows().next_power_of_two();
75        let padded_cols = matrix.num_cols().next_power_of_two();
76
77        // build dense vector representing the sparse padded matrix
78        let mut v = vec![zero.clone(); padded_rows * padded_cols];
79
80        for (row_i, row) in matrix.cells().enumerate() {
81            for (col_i, val) in row {
82                v[(padded_cols * row_i) + col_i] = val.clone();
83            }
84        }
85
86        // convert the dense vector into a mle
87        Self::from_evaluations_slice(n_vars, &v, zero)
88    }
89}
90
91impl<R: Default> DenseMultilinearExtension<R> {
92    pub fn from_evaluations_vec_pad(mut evaluations: Vec<R>) -> Self {
93        let len = evaluations.len();
94
95        evaluations.resize_with(len.next_power_of_two(), Default::default);
96
97        let num_vars = zinc_utils::log2(evaluations.len()) as usize;
98
99        Self {
100            evaluations,
101            num_vars,
102        }
103    }
104}
105
106impl<R: Clone> DenseMultilinearExtension<R> {
107    pub fn from_evaluations_vec_pad_with_zero(mut evaluations: Vec<R>, zero: &R) -> Self {
108        let len = evaluations.len();
109
110        evaluations.resize(len.next_power_of_two(), zero.clone());
111
112        let num_vars = zinc_utils::log2(evaluations.len()) as usize;
113
114        Self {
115            evaluations,
116            num_vars,
117        }
118    }
119}
120
121// Keeping Send bound here to match the FromParallelIterator impl
122impl<R: Send + Default> FromIterator<R> for DenseMultilinearExtension<R> {
123    fn from_iter<T: IntoIterator<Item = R>>(iter: T) -> Self {
124        Self::from_evaluations_vec_pad(iter.into_iter().collect())
125    }
126}
127
128impl<R> Deref for DenseMultilinearExtension<R> {
129    type Target = [R];
130
131    fn deref(&self) -> &Self::Target {
132        &self.evaluations
133    }
134}
135
136impl<R> DerefMut for DenseMultilinearExtension<R> {
137    fn deref_mut(&mut self) -> &mut Self::Target {
138        &mut self.evaluations
139    }
140}
141
142impl<R> IntoIterator for DenseMultilinearExtension<R> {
143    type Item = R;
144
145    type IntoIter = std::vec::IntoIter<R>;
146
147    fn into_iter(self) -> Self::IntoIter {
148        self.evaluations.into_iter()
149    }
150}
151
152#[cfg(feature = "parallel")]
153impl<R: Send + Default> FromParallelIterator<R> for DenseMultilinearExtension<R> {
154    fn from_par_iter<I>(par_iter: I) -> Self
155    where
156        I: IntoParallelIterator<Item = R>,
157    {
158        Self::from_evaluations_vec_pad(par_iter.into_par_iter().collect())
159    }
160}
161
162#[cfg(feature = "parallel")]
163impl<R: Send + Sync> IntoParallelIterator for DenseMultilinearExtension<R> {
164    type Iter = rayon::vec::IntoIter<R>;
165
166    type Item = R;
167
168    fn into_par_iter(self) -> Self::Iter {
169        self.evaluations.into_par_iter()
170    }
171}
172
173#[cfg(feature = "parallel")]
174impl<'data, R: Send + Sync> IntoParallelRefIterator<'data> for &'data DenseMultilinearExtension<R> {
175    type Iter = rayon::slice::Iter<'data, R>;
176
177    type Item = &'data R;
178
179    fn par_iter(&'data self) -> Self::Iter {
180        self.evaluations.par_iter()
181    }
182}
183
184#[cfg(feature = "parallel")]
185impl<'data, R: Send + Sync> IntoParallelRefMutIterator<'data>
186    for &'data mut DenseMultilinearExtension<R>
187{
188    type Iter = rayon::slice::IterMut<'data, R>;
189
190    type Item = &'data mut R;
191
192    fn par_iter_mut(&'data mut self) -> Self::Iter {
193        self.evaluations.par_iter_mut()
194    }
195}
196
197impl<R: SetElement> DenseMultilinearExtension<R> {
198    pub fn evaluate<C>(&self, cfg: &C, point: &[R]) -> Result<R, EvaluationError>
199    where
200        C: SemiringConfig<Element = R>,
201    {
202        if point.len() == self.num_vars {
203            Ok(self
204                .fixed_variables(cfg, point)
205                .into_iter()
206                .next()
207                .expect("Evaluations should not be empty"))
208        } else {
209            Err(EvaluationError::WrongPointWidth {
210                expected: self.num_vars,
211                actual: point.len(),
212            })
213        }
214    }
215
216    fn unary<G>(&mut self, f: G)
217    where
218        G: FnMut(&mut R),
219    {
220        self.iter_mut().for_each(f);
221    }
222
223    fn binary<G>(&mut self, other: &Self, mut f: G)
224    where
225        G: FnMut(&mut R, &R),
226    {
227        self.iter_mut().zip(other.iter()).for_each(|(a, b)| f(a, b));
228    }
229}
230
231impl<C: SemiringConfig> MultilinearExtension<C> for DenseMultilinearExtension<C::Element> {
232    #[allow(clippy::arithmetic_side_effects)]
233    fn fix_variables(&mut self, cfg: &C, partial_point: &[C::Element]) {
234        assert!(
235            partial_point.len() <= self.num_vars,
236            "too many partial points"
237        );
238
239        let nv = self.num_vars;
240        let dim = partial_point.len();
241
242        for i in 1..dim + 1 {
243            let r = &partial_point[i - 1];
244            for b in 0..1 << (nv - i) {
245                let left = &self[2 * b];
246                let right = &self[2 * b + 1];
247                // a = f(1) - f(0)
248                let a = cfg.checked_sub(right, left).expect("Subtraction overflow");
249                if !cfg.is_zero(&a) {
250                    // self[b] = f(0) + r * a
251                    let ar = cfg.checked_mul(&a, r).expect("Multiplication overflow");
252                    self[b] = cfg.checked_add(left, &ar).expect("Addition overflow");
253                } else {
254                    self[b] = left.clone();
255                };
256            }
257        }
258
259        self.evaluations.truncate(1 << (nv - dim));
260        self.num_vars = sub!(nv, dim);
261    }
262
263    fn fixed_variables(&self, cfg: &C, partial_point: &[C::Element]) -> Self {
264        let mut res = self.clone();
265        res.fix_variables(cfg, partial_point);
266        res
267    }
268}
269
270impl<R> MultilinearExtensionRand<R> for DenseMultilinearExtension<R>
271where
272    R: Send + Clone + Default,
273    StandardUniform: Distribution<R>,
274{
275    fn rand<G: Rng + ?Sized>(num_vars: usize, rng: &mut G) -> Self {
276        (0..1 << num_vars).map(|_| rng.random::<R>()).collect()
277    }
278}
279
280impl<T, I: SliceIndex<[T]>> Index<I> for DenseMultilinearExtension<T> {
281    type Output = I::Output;
282
283    fn index(&self, index: I) -> &Self::Output {
284        &self.evaluations[index]
285    }
286}
287
288impl<T, I: SliceIndex<[T]>> IndexMut<I> for DenseMultilinearExtension<T> {
289    fn index_mut(&mut self, index: I) -> &mut Self::Output {
290        &mut self.evaluations[index]
291    }
292}
293
294impl<R: Ring> Neg for DenseMultilinearExtension<R> {
295    type Output = Self;
296
297    fn neg(mut self) -> Self::Output {
298        self.unary(|v| *v = v.checked_neg().expect("Negation overflow"));
299        self
300    }
301}
302
303impl<R: Semiring> Add for DenseMultilinearExtension<R> {
304    type Output = Self;
305
306    #[allow(clippy::arithmetic_side_effects)]
307    fn add(self, rhs: Self) -> Self::Output {
308        self + &rhs
309    }
310}
311
312impl<R: Semiring> Add<&Self> for DenseMultilinearExtension<R> {
313    type Output = Self;
314
315    #[allow(clippy::arithmetic_side_effects)]
316    fn add(mut self, rhs: &Self) -> Self::Output {
317        self.binary(rhs, |a, b| *a += b);
318        self
319    }
320}
321
322impl<R: Semiring> Sub<&Self> for DenseMultilinearExtension<R> {
323    type Output = Self;
324
325    #[allow(clippy::arithmetic_side_effects)]
326    fn sub(mut self, rhs: &Self) -> Self::Output {
327        self.binary(rhs, |a, b| *a -= b);
328        self
329    }
330}
331
332impl<R: Semiring> Mul<&Self> for DenseMultilinearExtension<R> {
333    type Output = Self;
334
335    #[allow(clippy::arithmetic_side_effects)]
336    fn mul(mut self, rhs: &Self) -> Self::Output {
337        self.binary(rhs, |a, b| *a *= b);
338        self
339    }
340}
341
342impl<R: Semiring> Mul<R> for DenseMultilinearExtension<R> {
343    type Output = Self;
344
345    #[allow(clippy::arithmetic_side_effects)]
346    fn mul(mut self, rhs: R) -> Self::Output {
347        self.unary(|v| *v *= &rhs);
348        self
349    }
350}
351
352impl<R: Semiring> AddAssign<&Self> for DenseMultilinearExtension<R> {
353    #[allow(clippy::arithmetic_side_effects)]
354    fn add_assign(&mut self, rhs: &Self) {
355        self.binary(rhs, |a, b| *a += b);
356    }
357}
358
359impl<R: Semiring> SubAssign<&Self> for DenseMultilinearExtension<R> {
360    #[allow(clippy::arithmetic_side_effects)]
361    fn sub_assign(&mut self, rhs: &Self) {
362        self.binary(rhs, |a, b| *a -= b);
363    }
364}
365
366impl<R: Semiring> MulAssign<&Self> for DenseMultilinearExtension<R> {
367    #[allow(clippy::arithmetic_side_effects)]
368    fn mul_assign(&mut self, rhs: &Self) {
369        self.binary(rhs, |a, b| *a *= b);
370    }
371}
372
373impl<R: Semiring> AddAssign<(R, &Self)> for DenseMultilinearExtension<R> {
374    #[allow(clippy::arithmetic_side_effects)]
375    fn add_assign(&mut self, rhs: (R, &Self)) {
376        let coeff = rhs.0;
377        self.binary(rhs.1, |a, b| *a += b.clone() * &coeff);
378    }
379}
380
381pub fn project_coeffs<C, R>(
382    cfg: &C,
383    mle: DenseMultilinearExtension<R>,
384    sampled_value: &C::Element,
385) -> DenseMultilinearExtension<C::Element>
386where
387    C: FieldConfig,
388    R: ProjectableToField<C> + Send + Sync + 'static,
389{
390    let projection = R::prepare_projection(cfg, sampled_value);
391
392    DenseMultilinearExtension {
393        evaluations: cfg_into_iter!(mle.evaluations)
394            .map(|x| projection(&x))
395            .collect(),
396        num_vars: mle.num_vars,
397    }
398}
399
400pub trait CollectDenseMleWithZero: Iterator {
401    fn collect_dense_mle_with_zero(
402        self,
403        zero: &Self::Item,
404    ) -> DenseMultilinearExtension<Self::Item>;
405}
406
407impl<T> CollectDenseMleWithZero for T
408where
409    T: Iterator,
410    T::Item: Clone,
411{
412    fn collect_dense_mle_with_zero(
413        self,
414        zero: &Self::Item,
415    ) -> DenseMultilinearExtension<Self::Item> {
416        let evaluations = self.collect();
417
418        DenseMultilinearExtension::from_evaluations_vec_pad_with_zero(evaluations, zero)
419    }
420}
421
422#[cfg(test)]
423#[allow(
424    clippy::arithmetic_side_effects,
425    clippy::cast_possible_truncation,
426    clippy::cast_possible_wrap,
427    clippy::cast_sign_loss,
428    clippy::redundant_clone,
429    clippy::clone_on_copy
430)]
431mod tests {
432    use super::*;
433    use std::str::FromStr;
434
435    use crypto_bigint::{U256, const_monty_params};
436    use crypto_primitives::{
437        BaseFieldConfig, DenseRowMatrix, FixedConfig, LiftElementWithConfig,
438        ProjectElementWithConfig, SetConfig, crypto_bigint_const_monty::F256,
439        crypto_bigint_monty::MontyField, crypto_bigint_uint::Uint,
440    };
441    use proptest::prelude::*;
442
443    const LIMBS: usize = 4;
444
445    fn get_dyn_config(hex_modulus: &str) -> MontyField<LIMBS> {
446        let modulus =
447            Uint::from_str(&format!("0x{hex_modulus}")).expect("Invalid modulus hex string");
448        MontyField::new(&modulus).expect("Failed to create field config")
449    }
450
451    const MODULUS: &str = "0076F668F4274572E39A3EA8285319B5";
452    type F = MontyField<LIMBS>;
453    type E = <F as SetConfig>::Element;
454
455    fn any_e(cfg: F) -> impl Strategy<Value = E> + 'static {
456        any::<u128>().prop_map(move |v| cfg.project(&v))
457    }
458
459    fn any_dme() -> impl Strategy<Value = DenseMultilinearExtension<E>> {
460        let cfg = get_dyn_config(MODULUS);
461        (0usize..=5).prop_flat_map(move |n| {
462            let len = 1usize << n;
463            prop::collection::vec(any_e(cfg), len).prop_map(move |evals| {
464                DenseMultilinearExtension::from_evaluations_vec(n, evals, cfg.zero())
465            })
466        })
467    }
468
469    #[test]
470    fn test_dense_from_slice_and_indexing() {
471        let cfg = get_dyn_config(MODULUS);
472        let n_vars = 3usize;
473        let v = vec![cfg.project(&1u64), cfg.project(&2u64), cfg.project(&3u64)];
474        let dense = DenseMultilinearExtension::from_evaluations_slice(n_vars, &v, cfg.zero());
475        assert_eq!(dense.num_vars, n_vars);
476        let mut expected = v.clone();
477        expected.resize(1 << n_vars, cfg.zero());
478        assert_eq!(dense.evaluations, expected);
479        assert_eq!(dense[0], cfg.project(&1u64));
480        let mut d2 = dense.clone();
481        d2[1] = cfg.project(&99u64);
482        assert_eq!(d2[1], cfg.project(&99u64));
483    }
484
485    #[test]
486    fn test_fix_variables_and_evaluate() {
487        let cfg = get_dyn_config(MODULUS);
488        let evals: Vec<E> = [10u64, 20, 30, 40].iter().map(|v| cfg.project(v)).collect();
489        let mle = DenseMultilinearExtension::from_evaluations_vec(2, evals.clone(), cfg.zero());
490        for (idx, (x0, x1)) in [
491            (cfg.zero(), cfg.zero()),
492            (cfg.one(), cfg.zero()),
493            (cfg.zero(), cfg.one()),
494            (cfg.one(), cfg.one()),
495        ]
496        .iter()
497        .enumerate()
498        {
499            let val = mle
500                .clone()
501                .evaluate(&cfg, &[x0.clone(), x1.clone()])
502                .unwrap();
503            assert_eq!(val, evals[idx]);
504        }
505        let mut m2 = mle.clone();
506        m2.fix_variables(&cfg, &[cfg.one()]);
507        assert_eq!(m2.num_vars, 1);
508        assert_eq!(
509            m2.evaluations,
510            vec![cfg.project(&20u64), cfg.project(&40u64)]
511        );
512    }
513
514    #[test]
515    fn test_from_matrix_padding_and_conversion() {
516        let cfg = get_dyn_config(MODULUS);
517        let m: DenseRowMatrix<E> = DenseRowMatrix::from(vec![
518            vec![cfg.project(&5u64), cfg.zero()],
519            vec![cfg.zero(), cfg.zero()],
520            vec![cfg.zero(), cfg.project(&7u64)],
521        ]);
522        let dense = DenseMultilinearExtension::from_matrix(&m, cfg.zero());
523        assert_eq!(dense.num_vars, 3);
524        assert_eq!(dense[0], cfg.project(&5u64));
525        assert_eq!(dense[5], cfg.project(&7u64));
526        assert!(dense.iter().enumerate().all(|(i, v)| if i == 0 || i == 5 {
527            true
528        } else {
529            cfg.is_zero(v)
530        }));
531    }
532
533    #[test]
534    fn test_from_evaluations_vec_padding_branch_and_slice() {
535        let cfg = get_dyn_config(MODULUS);
536        // len < 2^n triggers padding branch
537        let evals = vec![cfg.project(&1u64), cfg.project(&2u64)];
538        let n = 2usize; // 4 expected
539        let d1 = DenseMultilinearExtension::from_evaluations_vec(n, evals.clone(), cfg.zero());
540        let mut expected = evals.clone();
541        expected.resize(1 << n, cfg.zero());
542        assert_eq!(d1.evaluations, expected);
543        let d2 = DenseMultilinearExtension::from_evaluations_slice(n, &evals, cfg.zero());
544        assert_eq!(d2.evaluations, expected);
545    }
546
547    #[test]
548    fn test_fix_variables_edge_cases_and_full_truncate() {
549        let cfg = get_dyn_config(MODULUS);
550        let evals: Vec<E> = [1u64, 2, 3, 4].iter().map(|v| cfg.project(v)).collect();
551        let d = DenseMultilinearExtension::from_evaluations_vec(2, evals.clone(), cfg.zero());
552        let d_fixed = d.fixed_variables(&cfg, &[]);
553        assert_eq!(d_fixed.num_vars, 2);
554        assert_eq!(d_fixed.evaluations, evals);
555
556        let evals: Vec<E> = [10u64, 20, 30, 40].iter().map(|v| cfg.project(v)).collect();
557        let mut d2 = DenseMultilinearExtension::from_evaluations_vec(2, evals, cfg.zero());
558        d2.fix_variables(&cfg, &[cfg.one(), cfg.zero()]);
559        assert_eq!(d2.num_vars, 0);
560        assert_eq!(d2.evaluations, vec![cfg.project(&20u64)]);
561    }
562
563    #[test]
564    fn test_evaluate_length_mismatch_returns_error() {
565        let cfg = get_dyn_config(MODULUS);
566        let evals: Vec<E> = [1u64, 2, 3, 4].iter().map(|v| cfg.project(v)).collect();
567        let d = DenseMultilinearExtension::from_evaluations_vec(2, evals, cfg.zero());
568        assert!(d.clone().evaluate(&cfg, &[cfg.one()]).is_err());
569        assert!(
570            d.evaluate(&cfg, &[cfg.one(), cfg.one(), cfg.zero()])
571                .is_err()
572        );
573    }
574
575    #[test]
576    fn test_zero_impl_for_dense_mle() {
577        let cfg = get_dyn_config(MODULUS);
578        let z: DenseMultilinearExtension<E> = DenseMultilinearExtension::zero_vars(cfg.zero());
579        assert_eq!(z.num_vars, 0);
580        assert_eq!(z.evaluations, vec![cfg.zero()]);
581    }
582
583    #[test]
584    fn test_arithmetic_ops_elementwise_add_sub_mul_and_neg() {
585        let a: DenseMultilinearExtension<i128> =
586            DenseMultilinearExtension::from_evaluations_vec(2, vec![1, 2, 3, 4], 0);
587        let b: DenseMultilinearExtension<i128> =
588            DenseMultilinearExtension::from_evaluations_vec(2, vec![5, 6, 7, 8], 0);
589
590        let sum = a.clone() + &b;
591        assert_eq!(sum.evaluations, vec![6, 8, 10, 12]);
592
593        let diff = b.clone() - &a;
594        assert_eq!(diff.evaluations, vec![4, 4, 4, 4]);
595
596        let prod = a.clone() * &b;
597        assert_eq!(prod.evaluations, vec![5, 12, 21, 32]);
598
599        // Neg
600        let neg_a = -a.clone();
601        assert_eq!(neg_a.evaluations, vec![-1, -2, -3, -4]);
602    }
603
604    #[test]
605    fn test_scalar_mul_and_assign_variants() {
606        let a: DenseMultilinearExtension<i128> =
607            DenseMultilinearExtension::from_evaluations_vec(2, vec![1, 2, 3, 4], 0);
608        let b: DenseMultilinearExtension<i128> =
609            DenseMultilinearExtension::from_evaluations_vec(2, vec![10, 20, 30, 40], 0);
610
611        let scaled = a.clone() * 3;
612        assert_eq!(scaled.evaluations, vec![3, 6, 9, 12]);
613
614        let mut c = a.clone();
615        c += &b;
616        assert_eq!(c.evaluations, vec![11, 22, 33, 44]);
617
618        c -= &b;
619        assert_eq!(c.evaluations, a.evaluations);
620
621        let mut d = a.clone();
622        d *= &b;
623        assert_eq!(d.evaluations, vec![10, 40, 90, 160]);
624
625        let mut e = a.clone();
626        e += (2, &b);
627        assert_eq!(e.evaluations, vec![21, 42, 63, 84]);
628    }
629
630    fn any_aligned_pair_with_point() -> impl Strategy<
631        Value = (
632            DenseMultilinearExtension<E>,
633            DenseMultilinearExtension<E>,
634            Vec<E>,
635        ),
636    > {
637        let cfg = get_dyn_config(MODULUS);
638        (0usize..=5).prop_flat_map(move |n| {
639            let len = 1usize << n;
640            prop::collection::vec(any_e(cfg), len).prop_flat_map(move |e1| {
641                let n2 = n;
642                prop::collection::vec(any_e(cfg), len).prop_flat_map(move |e2| {
643                    let n3 = n2;
644                    point_n(n3).prop_map({
645                        let e1v = e1.clone();
646                        let e2v = e2.clone();
647                        move |r| {
648                            (
649                                DenseMultilinearExtension::from_evaluations_vec(
650                                    n3,
651                                    e1v.clone(),
652                                    cfg.zero(),
653                                ),
654                                DenseMultilinearExtension::from_evaluations_vec(
655                                    n3,
656                                    e2v.clone(),
657                                    cfg.zero(),
658                                ),
659                                r,
660                            )
661                        }
662                    })
663                })
664            })
665        })
666    }
667    fn point_n(n: usize) -> impl Strategy<Value = Vec<E>> {
668        prop::collection::vec(any_e(get_dyn_config(MODULUS)), n)
669    }
670
671    proptest! {
672        #[test]
673        #[cfg_attr(miri, ignore)] // long running
674        fn prop_eval_add_is_linear((p1, p2, r) in any_aligned_pair_with_point()) {
675            let cfg = get_dyn_config(MODULUS);
676            // Elementwise sum via the config (raw elements have no std ops).
677            let sum = DenseMultilinearExtension {
678                num_vars: p1.num_vars,
679                evaluations: p1
680                    .evaluations
681                    .iter()
682                    .zip(p2.evaluations.iter())
683                    .map(|(a, b)| cfg.add(a, b))
684                    .collect(),
685            };
686            let lhs = sum.evaluate(&cfg, &r).unwrap();
687            let rhs = cfg.add(
688                &p1.evaluate(&cfg, &r).unwrap(),
689                &p2.evaluate(&cfg, &r).unwrap(),
690            );
691            prop_assert_eq!(lhs, rhs);
692        }
693
694        #[test]
695        #[cfg_attr(miri, ignore)] // long running
696        fn prop_fix_vars_commutes_with_eval((p, r, k) in any_dme().prop_flat_map(|p| {
697            let n = p.num_vars;
698            let point = point_n(n);
699            let ks = 0usize..=n;
700            (Just(p), point, ks)
701        })) {
702            let cfg = get_dyn_config(MODULUS);
703            let mut pfixed = p.clone();
704            pfixed.fix_variables(&cfg, &r[..k]);
705            let lhs = pfixed.evaluate(&cfg, &r[k..]).unwrap();
706            let rhs = p.evaluate(&cfg, &r).unwrap();
707            prop_assert_eq!(lhs, rhs);
708        }
709
710        #[test]
711        #[cfg_attr(miri, ignore)] // long running
712        fn prop_fix_vars_is_idempotent((p, k1, k2) in any_dme().prop_flat_map(|p| {
713            let n = p.num_vars;
714            let ks1 = 0usize..=n;
715            (Just(p), ks1).prop_flat_map(move |(p, k1)| {
716                let ks2 = 0usize..=n.saturating_sub(k1);
717                (Just(p), Just(k1), ks2)
718            })
719        }), r1 in prop::collection::vec(any_e(get_dyn_config(MODULUS)), 0..=8usize), r2 in prop::collection::vec(any_e(get_dyn_config(MODULUS)), 0..=8usize)) {
720            let cfg = get_dyn_config(MODULUS);
721            let mut p_step = p.clone();
722            p_step.fix_variables(&cfg, &r1[..k1.min(r1.len())]);
723            p_step.fix_variables(&cfg, &r2[..k2.min(r2.len())]);
724
725            let mut p_once = p.clone();
726            let mut concat = r1[..k1.min(r1.len())].to_vec();
727            concat.extend_from_slice(&r2[..k2.min(r2.len())]);
728            p_once.fix_variables(&cfg, &concat);
729
730            prop_assert_eq!(p_step.evaluations, p_once.evaluations);
731            prop_assert_eq!(p_step.num_vars, p_once.num_vars);
732        }
733    }
734
735    // Equivalence of the fixed-config path (`FixedConfig<ConstMontyField>`)
736    // and the dynamic-config path (`MontyField`) over the same modulus.
737    const_monty_params!(
738        ModQ,
739        U256,
740        "00dca94d8a1ecce3b6e8755d8999787d0524d8ca1ea755e7af84fb646fa31f27"
741    );
742    type CF = F256<ModQ>;
743    const MODULUS_Q: &str = "00dca94d8a1ecce3b6e8755d8999787d0524d8ca1ea755e7af84fb646fa31f27";
744
745    proptest! {
746        #[test]
747        #[cfg_attr(miri, ignore)] // long running
748        fn prop_mle_eval_fixed_cfg_matches_dyn_cfg((evals, point) in (0usize..=5).prop_flat_map(|n| {
749            (
750                prop::collection::vec(any::<u128>(), 1usize << n),
751                prop::collection::vec(any::<u128>(), n),
752            )
753        })) {
754            let n = point.len();
755            let fixed_cfg = FixedConfig::<CF>::default();
756            let dyn_cfg = get_dyn_config(MODULUS_Q);
757
758            let p_fixed = DenseMultilinearExtension::from_evaluations_vec(
759                n,
760                evals.iter().map(|v| CF::from(*v)).collect(),
761                fixed_cfg.zero(),
762            );
763            let p_dyn = DenseMultilinearExtension::from_evaluations_vec(
764                n,
765                evals.iter().map(|v| dyn_cfg.project(v)).collect(),
766                dyn_cfg.zero(),
767            );
768
769            let r_fixed: Vec<CF> = point.iter().map(|v| CF::from(*v)).collect();
770            let r_dyn: Vec<E> = point.iter().map(|v| dyn_cfg.project(v)).collect();
771
772            let lhs = fixed_cfg.lift(&p_fixed.evaluate(&fixed_cfg, &r_fixed).unwrap());
773            let rhs = dyn_cfg.lift(&p_dyn.evaluate(&dyn_cfg, &r_dyn).unwrap());
774            prop_assert_eq!(lhs, rhs);
775        }
776    }
777}
zinc_poly/mle/dense.rs

zinc_poly/mle/
dense.rs
