Struct BinarySubspace 

pub struct BinarySubspace<F, Data: Deref<Target = [F]> = Vec<F>> { /* private fields */ }

An $\mathbb{F}_2$-linear subspace of a binary field.

The subspace is the span of an ordered basis under XOR. The basis order fixes an order on the subspace’s own elements too.

Implementations

impl<F: BinaryField, Data: Deref<Target = [F]>> BinarySubspace<F, Data>

pub const fn new_unchecked(basis: Data) -> Self

Creates a new subspace from a vector of ordered basis elements.

This constructor does not check that the basis elements are linearly independent.

pub fn isomorphic<FIso>(&self) -> BinarySubspace<FIso>

where FIso: BinaryField + From<F>,

Creates a new subspace isomorphic to this one, over a different field type.

Maps each basis element into FIso via From, keeping the same order.

pub fn dim(&self) -> usize

Returns the dimension of the subspace.

pub fn basis(&self) -> &[F]

Returns the slice of ordered basis elements.

pub fn get(&self, index: usize) -> F

Returns the subspace element selected by index.

Bit i of index selects whether basis element i is included in the sum. Basis elements combine over $\mathbb{F}_2$, so “included” means XORed in.

Arguments

• index: which subspace element to return, in 0..2^dim.

Panics

Panics if index is at least 2^dim. Once dim reaches usize::BITS, every usize is below 2^dim, so no index can panic.

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

Returns an iterator over every element of the subspace, in index order.

Panics

Panics if the subspace’s dimension is at least usize::BITS. An index that large would not fit in a usize.

impl<F: BinaryField> BinarySubspace<F>

pub fn with_dim(dim: usize) -> Self

Creates a subspace spanned by the field’s first dim default basis elements.

Uses a prefix of the field’s own canonical $\mathbb{F}_2$ basis. So a smaller dimension is always a prefix of a larger one’s basis.

Panics

Panics if dim is greater than F::DEGREE.

pub fn reduce_dim(&self, dim: usize) -> Self

Creates a smaller subspace using a prefix of this subspace’s basis.

Panics

Panics if dim is greater than this subspace’s own dimension.

Trait Implementations

impl<F: Clone, Data: Clone + Deref<Target = [F]>> Clone for BinarySubspace<F, Data>

fn clone(&self) -> BinarySubspace<F, Data>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Debug, Data: Debug + Deref<Target = [F]>> Debug for BinarySubspace<F, Data>

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

Formats the value using the given formatter.

impl<F: BinaryField> Default for BinarySubspace<F>

fn default() -> Self

The default subspace spans the whole field, using its full canonical basis.

impl<F: Eq, Data: Eq + Deref<Target = [F]>> Eq for BinarySubspace<F, Data>

impl<F: BinaryField, Data: Deref<Target = [F]>> EvaluationDomain<F> for BinarySubspace<F, Data>

fn lagrange_evals<E: FieldOps + From<F>>(&self, z: &E) -> Vec<E>

Two sweeps build every entry without ever dividing:

    backward:   r_i <- w * prod_{j > i} (z - d_j)
    forward:    r_i <- r_i * prod_{j < i} (z - d_j)

That is about 4n multiplications and the single inversion the weight costs.

fn extrapolate<E: FieldOps + From<F>>(&self, values: &[E], z: &E) -> E

One prefix-product accumulator carries the whole sum in a single pass, so the extra space is constant rather than O(n).

fn lagrange_evals_buffer(&self, z: F) -> FieldBuffer<F>

The Lagrange basis at z, packed into a buffer instead of a vector.

impl<F: PartialEq, Data: PartialEq + Deref<Target = [F]>> PartialEq for BinarySubspace<F, Data>

fn eq(&self, other: &BinarySubspace<F, Data>) -> 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: PartialEq, Data: PartialEq + Deref<Target = [F]>> StructuralPartialEq for BinarySubspace<F, Data>