1use crate::FieldExt;
 2use serde::{Deserialize, Serialize};
 3
 4#[derive(Serialize, Deserialize)]
 5pub struct EqPoly<F: FieldExt> {
 6    t: Vec<F>,
 7}
 8
 9impl<F: FieldExt> EqPoly<F> {
10    pub fn new(t: Vec<F>) -> Self {
11        Self { t }
12    }
13
14    pub fn eval(&self, x: &[F]) -> F {
15        let mut result = F::ONE;
16        let one = F::ONE;
17
18        for i in 0..x.len() {
19            result *= self.t[i] * x[i] + (one - self.t[i]) * (one - x[i]);
20        }
21        result
22    }
23
24    // Copied from microsoft/Spartan
25    pub fn evals(&self) -> Vec<F> {
26        let ell = self.t.len(); // 4
27
28        let mut evals: Vec<F> = vec![F::ONE; 2usize.pow(ell as u32)];
29        let mut size = 1;
30        for j in 0..ell {
31            // in each iteration, we double the size of chis
32            size *= 2; // 2 4 8 16
33            for i in (0..size).rev().step_by(2) {
34                // copy each element from the prior iteration twice
35                let scalar = evals[i / 2]; // i = 0, 2, 4, 7
36                evals[i] = scalar * self.t[j]; // (1 * t0)(1 * t1)
37                evals[i - 1] = scalar - evals[i]; // 1 - (1 * t0)(1 * t1)
38            }
39        }
40        evals
41    }
42}
43
44#[cfg(test)]
45mod tests {
46    use super::*;
47    use crate::polynomial::sparse_ml_poly::SparseMLPoly;
48    use halo2curves::ff::Field;
49
50    type F = halo2curves::secp256k1::Fp;
51
52    pub fn dot_prod<F: FieldExt>(x: &[F], y: &[F]) -> F {
53        assert_eq!(x.len(), y.len());
54        let mut result = F::ZERO;
55        for i in 0..x.len() {
56            result += x[i] * y[i];
57        }
58        result
59    }
60
61    #[test]
62    fn test_eq_poly() {
63        let m = 4;
64        let t = (0..m).map(|i| F::from((i + 33) as u64)).collect::<Vec<F>>();
65        let eq_poly = EqPoly::new(t.clone());
66        eq_poly.evals();
67    }
68}