frontend/
digits.rs

1//! Module containing functions for deriving digital decompositions and building associated circuit
2//! components.
3use itertools::Itertools;
4use shared_types::Field;
5
6use remainder::utils::arithmetic::log2_ceil;
7
8use remainder::mle::evals::MultilinearExtension;
9
10/// Decompose a number into N digits in a given base, MSB first.
11/// Returns None iff the number is too large to fit in N digits.
12/// # Requires:
13///   + `log2(BASE) * N <= 64`
14///   + `BASE <= (1 << 16)`
15/// # Example
16/// ```
17/// # use frontend::digits::unsigned_decomposition;
18/// assert_eq!(unsigned_decomposition::<10, 3>(987), Some([9, 8, 7]));
19/// assert_eq!(unsigned_decomposition::<10, 3>(9870), None);
20/// ```
21pub fn unsigned_decomposition<const BASE: u64, const N: usize>(value: u64) -> Option<[u16; N]> {
22    debug_assert!(BASE <= (1 << 16));
23    debug_assert!(log2_ceil(BASE) * (N as u32) <= 64, "BASE * N must be <= 64");
24    let mut value = value;
25    let mut result = [0; N];
26    for i in (0..N).rev() {
27        result[i] = (value % BASE) as u16;
28        value /= BASE;
29    }
30    if value != 0 {
31        None
32    } else {
33        Some(result)
34    }
35}
36
37/// Decompose a number into N digits in a given BASE, MSB first, in the complementary representation, i.e.
38///   `value = b * BASE^N - (d[0] * BASE^(N-1) + d[1] * BASE^(N-2) + ... + d[N-1] * BASE^0)`
39/// where `(d, b)` is the result.
40/// Returns None iff value is out of range.
41/// # Requires:
42///   + `log2(BASE) * N <= 64`
43///   + `BASE <= (1 << 16)`
44/// # Example:
45/// ```
46/// # use frontend::digits::complementary_decomposition;
47/// let decomp = complementary_decomposition::<2, 3>(3);
48/// assert_eq!(decomp, Some(([1, 0, 1], true)));
49/// ```
50pub fn complementary_decomposition<const BASE: u64, const N: usize>(
51    value: i64,
52) -> Option<([u16; N], bool)> {
53    debug_assert!(BASE <= (1 << 16));
54    debug_assert!(log2_ceil(BASE) * (N as u32) <= 64, "BASE * N must be <= 64");
55    let pow = (BASE as u128).pow(N as u32);
56    if (value >= 0 && (value as u128) > pow) || (value < 0 && (-value as u128) > pow - 1) {
57        return None;
58    }
59    let (val_to_decomp, bit) = if value > 0 {
60        ((pow - (value as u128)), true)
61    } else {
62        ((-value) as u128, false)
63    };
64    // unwrap() guaranteed given the checks on already made
65    Some((
66        unsigned_decomposition::<BASE, N>(val_to_decomp as u64).unwrap(),
67        bit,
68    ))
69}
70
71/// Convert a slice of digits to a slice of field elements.
72/// # Example:
73/// ```
74/// use shared_types::Fr;
75/// use frontend::digits::digits_to_field;
76/// assert_eq!(digits_to_field::<Fr, 3>(&[1, 2, 3]), [Fr::from(1), Fr::from(2), Fr::from(3)]);
77/// ```
78pub fn digits_to_field<F: Field, const N: usize>(digits: &[u16; N]) -> [F; N] {
79    digits
80        .iter()
81        .map(|x| F::from(*x as u64))
82        .collect::<Vec<_>>()
83        .try_into()
84        .unwrap()
85}
86
87/// Helper function that converts a `Vec<[F; N]>` into a `[MultilinearExtension<F>; N]`, i.e.
88/// that changes the order of the enumeration by iterating first over the inner
89/// index, then the outer index.
90/// # Example:
91/// ```
92/// use shared_types::Fr;
93/// use frontend::digits::to_slice_of_mles;
94/// let inputs = vec![
95///     [Fr::from(1), Fr::from(2), Fr::from(3)],
96///     [Fr::from(4), Fr::from(5), Fr::from(6)],
97/// ];
98/// let expected_evals = [
99///     vec![Fr::from(1), Fr::from(4)],
100///     vec![Fr::from(2), Fr::from(5)],
101///     vec![Fr::from(3), Fr::from(6)],
102/// ];
103/// let actual_evals: Vec<Vec<Fr>> = to_slice_of_mles(inputs).into_iter().map(|mle| mle.to_vec()).collect();
104/// assert_eq!(actual_evals, expected_evals);
105/// ```
106pub fn to_slice_of_mles<F: Field, const N: usize>(
107    inputs: Vec<[F; N]>,
108) -> [MultilinearExtension<F>; N] {
109    let mut result_evals: [Vec<F>; N] = vec![Vec::new(); N].try_into().unwrap();
110    for subarray in inputs {
111        for (i, element) in subarray.iter().enumerate() {
112            result_evals[i].push(*element);
113        }
114    }
115    let result_mles: [MultilinearExtension<F>; N] = result_evals
116        .into_iter()
117        .map(|evals| MultilinearExtension::new(evals))
118        .collect_vec()
119        .try_into()
120        .unwrap();
121    result_mles
122}
123
124#[test]
125fn test_unsigned_decomposition() {
126    assert_eq!(unsigned_decomposition::<10, 3>(987), Some([9, 8, 7]));
127    assert_eq!(unsigned_decomposition::<10, 3>(0), Some([0, 0, 0]));
128    assert_eq!(unsigned_decomposition::<2, 3>(1), Some([0, 0, 1]));
129    assert_eq!(unsigned_decomposition::<2, 3>(4), Some([1, 0, 0]));
130    assert_eq!(unsigned_decomposition::<2, 3>(8), None);
131}
132
133#[test]
134fn test_complementary_decomposition() {
135    // base 2
136    assert_eq!(
137        complementary_decomposition::<2, 3>(1),
138        Some(([1, 1, 1], true))
139    );
140    assert_eq!(
141        complementary_decomposition::<2, 3>(3),
142        Some(([1, 0, 1], true))
143    );
144    assert_eq!(
145        complementary_decomposition::<2, 3>(8),
146        Some(([0, 0, 0], true))
147    );
148    assert_eq!(
149        complementary_decomposition::<2, 3>(0),
150        Some(([0, 0, 0], false))
151    );
152    assert_eq!(
153        complementary_decomposition::<2, 3>(-1),
154        Some(([0, 0, 1], false))
155    );
156    assert_eq!(
157        complementary_decomposition::<2, 3>(-3),
158        Some(([0, 1, 1], false))
159    );
160    assert_eq!(complementary_decomposition::<2, 3>(-8), None);
161    assert_eq!(complementary_decomposition::<2, 3>(9), None);
162    // base 10
163    assert_eq!(
164        complementary_decomposition::<10, 3>(-987),
165        Some(([9, 8, 7], false))
166    );
167    assert_eq!(
168        complementary_decomposition::<10, 3>(987),
169        Some(([0, 1, 3], true))
170    );
171    assert_eq!(
172        complementary_decomposition::<10, 3>(0),
173        Some(([0, 0, 0], false))
174    );
175    assert_eq!(complementary_decomposition::<10, 3>(-1000), None);
176    assert_eq!(complementary_decomposition::<10, 3>(1001), None);
177}
frontend/digits.rs

frontend/
digits.rs
