shared_types/utils/
bookkeeping_table.rs

1use crate::Field;
2use itertools::Itertools;
3
4/// Initializes with every iterated combination of the (binary)
5/// variables in `challenge_coord`.
6///
7/// In other words, if `challenge_coord` is [r_1, r_2, r_3] then
8/// `initialize_tensor` should output the following:
9///
10/// (1 - r_1) * (1 - r_2) * (1 - r_3),
11/// (1 - r_1) * (1 - r_2) * (r_3),
12/// (1 - r_1) * (r_2) * (1 - r_3),
13/// (1 - r_1) * (r_2) * (r_3),
14/// (r_1) * (1 - r_2) * (1 - r_3),
15/// (r_1) * (1 - r_2) * (r_3),
16/// (r_1) * (r_2) * (1 - r_3),
17/// (r_1) * (r_2) * (r_3),
18///
19/// ## Arguments
20/// * `challenge_coord` - Challenge point to be expanded in big-endian.
21pub fn initialize_tensor<F: Field>(challenge_coord: &[F]) -> Vec<F> {
22    let mut cur_table = Vec::with_capacity(1 << challenge_coord.len());
23    cur_table.push(F::ONE);
24    if !challenge_coord.is_empty() {
25        // Dynamic programming algorithm in Tha13 for computing these
26        // equality values and returning them as a vector.
27
28        // Iterate through remaining challenge coordinates in reverse,
29        // starting with the least significant variable.
30        for challenge in challenge_coord.iter().rev() {
31            let (one_minus_r, r) = (F::ONE - challenge, *challenge);
32
33            // Double the size of `cur_table` to hold new values.
34            let len = cur_table.len();
35            cur_table.resize(len * 2, F::ZERO);
36
37            for i in 0..len {
38                cur_table[i + len] = cur_table[i] * r;
39                cur_table[i] *= one_minus_r;
40            }
41        }
42    }
43    cur_table
44}
45
46/// Similar to [initialize_tensor], but takes the RLC of tensors over
47/// a vector of challenge coordinates given the random coefficients.
48pub fn initialize_tensor_rlc<F: Field>(challenge_coord_vec: &[&[F]], random_coeff: &[F]) -> Vec<F> {
49    challenge_coord_vec
50        .iter()
51        .skip(1)
52        .zip(random_coeff.iter().skip(1))
53        .fold(
54            initialize_tensor(challenge_coord_vec[0])
55                .iter()
56                .map(|elem| *elem * random_coeff[0])
57                .collect_vec(),
58            |acc, (elem, random_coeff)| {
59                acc.iter()
60                    .zip(initialize_tensor(elem).iter())
61                    .map(|(acc_elem, next_elem)| *acc_elem + (*next_elem * random_coeff))
62                    .collect_vec()
63            },
64        )
65}
shared_types/utils/bookkeeping_table.rs

shared_types/utils/
bookkeeping_table.rs
