1// code forked from
  2// https://github.com/EspressoSystems/hyperplonk/blob/main/arithmetic/src/multilinear_polynomial.rs
  3//
  4// Copyright (c) 2023 Espresso Systems (espressosys.com)
  5// This file is part of the HyperPlonk library.
  6
  7// You should have received a copy of the MIT License
  8// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
  9
 10use ark_ff::Field;
 11#[cfg(feature = "parallel")]
 12use rayon::prelude::{IndexedParallelIterator, IntoParallelRefMutIterator, ParallelIterator};
 13
 14pub use ark_poly::DenseMultilinearExtension;
 15
 16pub fn fix_variables<F: Field>(
 17    poly: &DenseMultilinearExtension<F>,
 18    partial_point: &[F],
 19) -> DenseMultilinearExtension<F> {
 20    assert!(
 21        partial_point.len() <= poly.num_vars,
 22        "invalid size of partial point"
 23    );
 24    let nv = poly.num_vars;
 25    let mut poly = poly.evaluations.to_vec();
 26    let dim = partial_point.len();
 27    // evaluate single variable of partial point from left to right
 28    for (i, point) in partial_point.iter().enumerate().take(dim) {
 29        poly = fix_one_variable_helper(&poly, nv - i, point);
 30    }
 31
 32    DenseMultilinearExtension::<F>::from_evaluations_slice(nv - dim, &poly[..(1 << (nv - dim))])
 33}
 34
 35fn fix_one_variable_helper<F: Field>(data: &[F], nv: usize, point: &F) -> Vec<F> {
 36    let mut res = vec![F::zero(); 1 << (nv - 1)];
 37
 38    // evaluate single variable of partial point from left to right
 39    #[cfg(not(feature = "parallel"))]
 40    for i in 0..(1 << (nv - 1)) {
 41        res[i] = data[i << 1] + (data[(i << 1) + 1] - data[i << 1]) * point;
 42    }
 43
 44    #[cfg(feature = "parallel")]
 45    res.par_iter_mut().enumerate().for_each(|(i, x)| {
 46        *x = data[i << 1] + (data[(i << 1) + 1] - data[i << 1]) * point;
 47    });
 48
 49    res
 50}
 51
 52pub fn evaluate_no_par<F: Field>(poly: &DenseMultilinearExtension<F>, point: &[F]) -> F {
 53    assert_eq!(poly.num_vars, point.len());
 54    fix_variables_no_par(poly, point).evaluations[0]
 55}
 56
 57fn fix_variables_no_par<F: Field>(
 58    poly: &DenseMultilinearExtension<F>,
 59    partial_point: &[F],
 60) -> DenseMultilinearExtension<F> {
 61    assert!(
 62        partial_point.len() <= poly.num_vars,
 63        "invalid size of partial point"
 64    );
 65    let nv = poly.num_vars;
 66    let mut poly = poly.evaluations.to_vec();
 67    let dim = partial_point.len();
 68    // evaluate single variable of partial point from left to right
 69    for i in 1..dim + 1 {
 70        let r = partial_point[i - 1];
 71        for b in 0..(1 << (nv - i)) {
 72            poly[b] = poly[b << 1] + (poly[(b << 1) + 1] - poly[b << 1]) * r;
 73        }
 74    }
 75    DenseMultilinearExtension::from_evaluations_slice(nv - dim, &poly[..(1 << (nv - dim))])
 76}
 77
 78/// Given multilinear polynomial `p(x)` and s `s`, compute `s*p(x)`
 79pub fn scalar_mul<F: Field>(
 80    poly: &DenseMultilinearExtension<F>,
 81    s: &F,
 82) -> DenseMultilinearExtension<F> {
 83    DenseMultilinearExtension {
 84        evaluations: poly.evaluations.iter().map(|e| *e * s).collect(),
 85        num_vars: poly.num_vars,
 86    }
 87}
 88
 89/// Test-only methods used in virtual_polynomial.rs
 90#[cfg(test)]
 91pub mod tests {
 92    use super::*;
 93    use ark_ff::PrimeField;
 94    use ark_std::rand::RngCore;
 95    use ark_std::{end_timer, start_timer};
 96    use std::sync::Arc;
 97
 98    pub fn fix_last_variables<F: PrimeField>(
 99        poly: &DenseMultilinearExtension<F>,
100        partial_point: &[F],
101    ) -> DenseMultilinearExtension<F> {
102        assert!(
103            partial_point.len() <= poly.num_vars,
104            "invalid size of partial point"
105        );
106        let nv = poly.num_vars;
107        let mut poly = poly.evaluations.to_vec();
108        let dim = partial_point.len();
109        // evaluate single variable of partial point from left to right
110        for (i, point) in partial_point.iter().rev().enumerate().take(dim) {
111            poly = fix_last_variable_helper(&poly, nv - i, point);
112        }
113
114        DenseMultilinearExtension::<F>::from_evaluations_slice(nv - dim, &poly[..(1 << (nv - dim))])
115    }
116
117    fn fix_last_variable_helper<F: Field>(data: &[F], nv: usize, point: &F) -> Vec<F> {
118        let half_len = 1 << (nv - 1);
119        let mut res = vec![F::zero(); half_len];
120
121        // evaluate single variable of partial point from left to right
122        #[cfg(not(feature = "parallel"))]
123        for b in 0..half_len {
124            res[b] = data[b] + (data[b + half_len] - data[b]) * point;
125        }
126
127        #[cfg(feature = "parallel")]
128        res.par_iter_mut().enumerate().for_each(|(i, x)| {
129            *x = data[i] + (data[i + half_len] - data[i]) * point;
130        });
131
132        res
133    }
134
135    /// Sample a random list of multilinear polynomials.
136    /// Returns
137    /// - the list of polynomials,
138    /// - its sum of polynomial evaluations over the boolean hypercube.
139    #[cfg(test)]
140    pub fn random_mle_list<F: PrimeField, R: RngCore>(
141        nv: usize,
142        degree: usize,
143        rng: &mut R,
144    ) -> (Vec<Arc<DenseMultilinearExtension<F>>>, F) {
145        let start = start_timer!(|| "sample random mle list");
146        let mut multiplicands = Vec::with_capacity(degree);
147        for _ in 0..degree {
148            multiplicands.push(Vec::with_capacity(1 << nv))
149        }
150        let mut sum = F::zero();
151
152        for _ in 0..(1 << nv) {
153            let mut product = F::one();
154
155            for e in multiplicands.iter_mut() {
156                let val = F::rand(rng);
157                e.push(val);
158                product *= val;
159            }
160            sum += product;
161        }
162
163        let list = multiplicands
164            .into_iter()
165            .map(|x| Arc::new(DenseMultilinearExtension::from_evaluations_vec(nv, x)))
166            .collect();
167
168        end_timer!(start);
169        (list, sum)
170    }
171
172    // Build a randomize list of mle-s whose sum is zero.
173    #[cfg(test)]
174    pub fn random_zero_mle_list<F: PrimeField, R: RngCore>(
175        nv: usize,
176        degree: usize,
177        rng: &mut R,
178    ) -> Vec<Arc<DenseMultilinearExtension<F>>> {
179        let start = start_timer!(|| "sample random zero mle list");
180
181        let mut multiplicands = Vec::with_capacity(degree);
182        for _ in 0..degree {
183            multiplicands.push(Vec::with_capacity(1 << nv))
184        }
185        for _ in 0..(1 << nv) {
186            multiplicands[0].push(F::zero());
187            for e in multiplicands.iter_mut().skip(1) {
188                e.push(F::rand(rng));
189            }
190        }
191
192        let list = multiplicands
193            .into_iter()
194            .map(|x| Arc::new(DenseMultilinearExtension::from_evaluations_vec(nv, x)))
195            .collect();
196
197        end_timer!(start);
198        list
199    }
200}