Function expand_subset_sums_array

pub fn expand_subset_sums_array<F: Field, const N: usize, const N_EXP2: usize>(
    elems: [F; N],
) -> [F; N_EXP2]

Expands an array of field elements into all possible subset sums.

For an input array [a, b, c], this computes all possible sums of subsets: [0, a, b, a+b, c, a+c, b+c, a+b+c]

This is used to create lookup tables for the Method of Four Russians optimization, where we precompute all possible combinations of a small set of values to avoid doing the additions at runtime.

Type Parameters

• F - The field element type
• N - Size of the input array
• N_EXP2 - Size of the output array, must be 2^N

Arguments

• elems - Input array of N field elements

Returns

An array of size N_EXP2 containing all possible subset sums of the input elements

Preconditions

• N_EXP2 must equal 2^N

Example

let input = [F::ONE, F::from(2)];
let sums = expand_subset_sums_array(input);
// sums = [F::ZERO, F::ONE, F::from(2), F::from(3)]