Struct Evaluations 

pub struct Evaluations<F: Field> {
    evals: BitPackedVector<F>,
    num_vars: usize,
    zero: F,
}

Stores a boolean function f: {0, 1}^n -> F represented as a list of up to 2^n evaluations of f on the boolean hypercube. The n variables are indexed from 0 to n-1 throughout the lifetime of the object.

Fields

evals: BitPackedVector<F>

To understand how evaluations are stored, let’s index f’s input bits as follows: f(b_0, b_1, ..., b_{n-1}). Evaluations are ordered using the bit-string b_0b_1...b_{n-2}b_{n-1} as key. This ordering is sometimes referred to as “big-endian” due to its resemblance to big-endian byte ordering. A suffix of contiguous evaluations all equal to F::ZERO may be omitted in this internal representation but this struct is not responsible for maintaining this property at all times.

Example

• The evaluations of a 2-dimensional function are stored in the following order: [ f(0, 0), f(0, 1), f(1, 0), f(1, 1) ].
• The evaluation table [ 1, 0, 5, 0 ] may be stored as [1, 0, 5] by omitting the trailing zero. Note that both representations are valid.

num_vars: usize

Number of input variables to f. Invariant: 0 <= evals.len() <= 2^num_vars. The length can be less than 2^num_vars due to suffix omission.

zero: F

TODO(Makis): Is there a better way to handle this?? When accessing an element of the bookkeping table, we return a reference to a field element. In case the element is stored implicitly as a missing entry, we need someone to own the “zero” of the field. If I make this a const, I’m not sure how to initialize it.

Implementations

impl<F: Field> Evaluations<F>

pub fn new_zero() -> Self

Returns a representation of the constant function on zero variables equal to F::ZERO.

pub fn new(num_vars: usize, evals: Vec<F>) -> Self

Builds an evaluation representation for a function f: {0, 1}^num_vars -> F from a vector of evaluations in big-endian order (see documentation comment for Self::evals for explanation).

Example

For a function f: {0, 1}^2 -> F, an evaluations table may be built as: Evaluations::new(2, vec![ f(0, 0), f(0, 1), f(1, 0), f(1, 1) ]).

An example of suffix omission is when f(1, 0) == f(1, 1) == F::ZERO. In that case those zero values may be omitted and the following statement generates an equivalent representation: Evaluations::new(2, vec![ f(0, 0), f(0, 1) ]).

pub fn new_from_little_endian(num_vars: usize, evals: &[F]) -> Self

Builds an evaluation representation for a function f: {0, 1}^num_vars -> F from a vector of evaluations in little-endian order (see documentation comment for Self::evals for explanation).

Example

For a function f: {0, 1}^2 -> F, an evaluations table may be built as: Evaluations::new_from_little_endian(2, vec![ f(0, 0), f(1, 0), f(0, 1), f(1, 1) ]).

pub fn num_vars(&self) -> usize

Returns the number of variables of the current Evalations.

pub fn is_fully_bound(&self) -> bool

Returns true if the boolean function has not free variables. Equivalent to checking whether that Self::num_vars is equal to zero.

pub fn first(&self) -> F

Returns the first element of the bookkeeping table. This operation should always be successful because even in the case that Self::num_vars is zero, there is a non-zero number of vertices on the boolean hypercube and hence there’s at least one evaluation stored in the bookkeeping table, either explicitly as a value inside Self::evals, or implicitly if it’s a F::ZERO that has been pruned as part of a zero suffix.

pub fn value(&self) -> F

If self represents a fully-bound boolean function (i.e. Self::num_vars is zero), it returns its value. Otherwise panics.

pub fn iter(&self) -> EvaluationsIterator<'_, F>

Returns an iterator that traverses the evaluations in “big-endian” order.

pub fn len(&self) -> usize

Temporary function returning the length of the internal representation.

pub fn get(&self, idx: usize) -> Option<F>

Temporary function for accessing a the idx-th element in the internal representation.

fn equiv_repr(evals1: &BitPackedVector<F>, evals2: &BitPackedVector<F>) -> bool

Checks whether its arguments correspond to equivalent representations of the same list of evaluations. Two representations are equivalent if omitting the longest contiguous suffix of F::ZEROs from each results in the same vectors.

pub fn flip_endianess(num_bits: usize, values: &[F]) -> Vec<F>

Sorts the elements of values by their 0-based index transformed by mirroring the num_bits LSBs. This operation effectively flips the “endianess” of the index ordering. If values.len() < 2^num_bits, the missing values are assumed to be zeros. The resulting vector is always of size 2^num_bits.

Example

use remainder::mle::evals::Evaluations;
use shared_types::Fr;
assert_eq!(Evaluations::flip_endianess(
    2,
    &[Fr::from(1), Fr::from(2), Fr::from(3), Fr::from(4)]),
    vec![ Fr::from(1), Fr::from(3), Fr::from(2), Fr::from(4) ]
);
assert_eq!(Evaluations::flip_endianess(
    2,
    &[ Fr::from(1), Fr::from(2) ]),
    vec![ Fr::from(1), Fr::from(0), Fr::from(2), Fr::from(0) ]
);

Trait Implementations

impl<F: Clone + Field> Clone for Evaluations<F>

fn clone(&self) -> Evaluations<F>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug + Field> Debug for Evaluations<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de, F> Deserialize<'de> for Evaluations<F>

where F: Field,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<F: PartialEq + Field> PartialEq for Evaluations<F>

fn eq(&self, other: &Evaluations<F>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<F> Serialize for Evaluations<F>

where F: Field,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<F: Field> Zeroize for Evaluations<F>

fn zeroize(&mut self)

Zero out this object from memory using Rust intrinsics which ensure the zeroization operation is not “optimized away” by the compiler.

impl<F: Field> StructuralPartialEq for Evaluations<F>