ark_poly/evaluations/multivariate/multilinear/
mod.rs

1mod dense;
2mod sparse;
3
4pub use dense::DenseMultilinearExtension;
5pub use sparse::SparseMultilinearExtension;
6
7use ark_std::{
8    fmt::Debug,
9    hash::Hash,
10    ops::{Add, AddAssign, Index, Neg, SubAssign},
11    vec::*,
12};
13
14use ark_ff::{Field, Zero};
15
16use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
17use ark_std::rand::Rng;
18
19use crate::Polynomial;
20
21#[cfg(all(
22    target_has_atomic = "8",
23    target_has_atomic = "16",
24    target_has_atomic = "32",
25    target_has_atomic = "64",
26    target_has_atomic = "ptr"
27))]
28type DefaultHasher = ahash::AHasher;
29
30#[cfg(not(all(
31    target_has_atomic = "8",
32    target_has_atomic = "16",
33    target_has_atomic = "32",
34    target_has_atomic = "64",
35    target_has_atomic = "ptr"
36)))]
37type DefaultHasher = fnv::FnvHasher;
38
39/// This trait describes an interface for the multilinear extension
40/// of an array.
41/// The latter is a multilinear polynomial represented in terms of its
42/// evaluations over the domain {0,1}^`num_vars` (i.e. the Boolean hypercube).
43///
44/// Index represents a point, which is a vector in {0,1}^`num_vars` in little
45/// endian form. For example, `0b1011` represents `P(1,1,0,1)`
46pub trait MultilinearExtension<F: Field>:
47    Sized
48    + Clone
49    + Debug
50    + Hash
51    + PartialEq
52    + Eq
53    + Add
54    + Neg
55    + Zero
56    + CanonicalSerialize
57    + CanonicalDeserialize
58    + for<'a> AddAssign<&'a Self>
59    + for<'a> AddAssign<(F, &'a Self)>
60    + for<'a> SubAssign<&'a Self>
61    + Index<usize>
62    + Polynomial<F, Point = Vec<F>>
63{
64    /// Returns the number of variables in `self`
65    fn num_vars(&self) -> usize;
66
67    /// Outputs an `l`-variate multilinear extension where value of evaluations
68    /// are sampled uniformly at random.
69    fn rand<R: Rng>(num_vars: usize, rng: &mut R) -> Self;
70
71    /// Relabel the point by swapping `k` scalars from positions `a..a+k` to
72    /// positions `b..b+k`, and from position `b..b+k` to position `a..a+k`
73    /// in vector.
74    ///
75    /// This function turns `P(x_1,...,x_a,...,x_{a+k - 1},...,x_b,...,x_{b+k - 1},...,x_n)`
76    /// to `P(x_1,...,x_b,...,x_{b+k - 1},...,x_a,...,x_{a+k - 1},...,x_n)`
77    fn relabel(&self, a: usize, b: usize, k: usize) -> Self;
78
79    /// Reduce the number of variables of `self` by fixing the
80    /// `partial_point.len()` variables at `partial_point`.
81    fn fix_variables(&self, partial_point: &[F]) -> Self;
82
83    /// Returns a list of evaluations over the domain, which is the boolean
84    /// hypercube. The evaluations are in little-endian order.
85    fn to_evaluations(&self) -> Vec<F>;
86}
87
88/// swap the bits of `x` from position `a..a+n` to `b..b+n` and from `b..b+n` to `a..a+n` in little endian order
89pub(crate) fn swap_bits(x: usize, a: usize, b: usize, n: usize) -> usize {
90    let a_bits = (x >> a) & ((1usize << n) - 1);
91    let b_bits = (x >> b) & ((1usize << n) - 1);
92    let local_xor_mask = a_bits ^ b_bits;
93    let global_xor_mask = (local_xor_mask << a) | (local_xor_mask << b);
94    x ^ global_xor_mask
95}
ark_poly/evaluations/multivariate/multilinear/mod.rs

ark_poly/evaluations/multivariate/multilinear/
mod.rs
