Skip to main content

expand_subset_products

Function expand_subset_products 

Source
pub fn expand_subset_products<P: PackedField>(elems: &[P]) -> Vec<P>
Expand description

Expands elems into all 2^elems.len() subset products, indexed by subset bitmask.

The multiplicative counterpart of expand_subset_sums. Entry mask holds the product of elems[i] over every bit i set in mask. So entry 0 is one and entry 2^i is elems[i].

This is the tensor expansion (1, elems[0]) x ... x (1, elems[k-1]). A caller holding k factors of a product basis recovers all 2^k basis elements from them.

Each entry costs one multiplication. Multiplying a subset directly would cost one per set bit.

ยงPreconditions

  • elems.len() must be less than usize::BITS