1//! This module implements useful functions for the permutation check protocol.
 2
 3use crate::errors::PolyIOPErrors;
 4use arithmetic::identity_permutation_mle;
 5use ark_ff::PrimeField;
 6use ark_poly::DenseMultilinearExtension;
 7use ark_std::{end_timer, start_timer};
 8use std::rc::Rc;
 9
10/// Returns the evaluations of two MLEs:
11/// - numerator
12/// - denominator
13///
14///  where
15///  - beta and gamma are challenges
16///  - f(x), g(x), s_id(x), s_perm(x) are mle-s
17///
18/// - numerator is the MLE for `f(x) + \beta s_id(x) + \gamma`
19/// - denominator is the MLE for `g(x) + \beta s_perm(x) + \gamma`
20#[allow(clippy::type_complexity)]
21pub(super) fn computer_num_and_denom<F: PrimeField>(
22    beta: &F,
23    gamma: &F,
24    fx: &DenseMultilinearExtension<F>,
25    gx: &DenseMultilinearExtension<F>,
26    s_perm: &DenseMultilinearExtension<F>,
27) -> Result<
28    (
29        Rc<DenseMultilinearExtension<F>>,
30        Rc<DenseMultilinearExtension<F>>,
31    ),
32    PolyIOPErrors,
33> {
34    let start = start_timer!(|| "compute numerator and denominator");
35
36    let num_vars = fx.num_vars;
37    let mut numerator_evals = vec![];
38    let mut denominator_evals = vec![];
39    let s_id = identity_permutation_mle::<F>(num_vars);
40
41    for (&fi, (&gi, (&s_id_i, &s_perm_i))) in
42        fx.iter().zip(gx.iter().zip(s_id.iter().zip(s_perm.iter())))
43    {
44        let numerator = fi + *beta * s_id_i + gamma;
45        let denominator = gi + *beta * s_perm_i + gamma;
46
47        numerator_evals.push(numerator);
48        denominator_evals.push(denominator);
49    }
50    let numerator = Rc::new(DenseMultilinearExtension::from_evaluations_vec(
51        num_vars,
52        numerator_evals,
53    ));
54    let denominator = Rc::new(DenseMultilinearExtension::from_evaluations_vec(
55        num_vars,
56        denominator_evals,
57    ));
58
59    end_timer!(start);
60    Ok((numerator, denominator))
61}