qfall_math/integer/mat_poly_over_z/sample/
binomial.rs

1// Copyright © 2023 Niklas Siemer
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! This module contains algorithms for sampling
10//! according to the binomial distribution.
11
12use crate::{
13    error::MathError,
14    integer::{MatPolyOverZ, PolyOverZ, Z},
15    rational::Q,
16    traits::{MatrixDimensions, MatrixSetEntry, SetCoefficient},
17    utils::{index::evaluate_index, sample::binomial::BinomialSampler},
18};
19use std::fmt::Display;
20
21impl MatPolyOverZ {
22    /// Outputs a [`MatPolyOverZ`] instance with entries chosen according to the binomial
23    /// distribution parameterized by `n` and `p`.
24    ///
25    /// Parameters:
26    /// - `num_rows`: specifies the number of rows the new matrix should have
27    /// - `num_cols`: specifies the number of columns the new matrix should have
28    /// - `max_degree`: specifies the maximum length of all polynomials in the matrix,
29    ///   i.e. the maximum number of coefficients any polynomial in the matrix can have
30    /// - `n`: specifies the number of trials
31    /// - `p`: specifies the probability of success
32    ///
33    /// Returns a new [`MatPolyOverZ`] instance with entries chosen
34    /// according to the binomial distribution or a [`MathError`]
35    /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`],
36    /// or the dimensions of the matrix were chosen too small.
37    ///
38    /// # Examples
39    /// ```
40    /// use qfall_math::integer::MatPolyOverZ;
41    ///
42    /// let sample = MatPolyOverZ::sample_binomial(2, 2, 5, 2, 0.5).unwrap();
43    /// ```
44    ///
45    /// # Errors and Failures
46    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
47    ///   if `n < 0` or `p ∉ (0,1)`.
48    /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
49    ///   if `n` does not fit into an [`i64`].
50    ///
51    /// # Panics ...
52    /// - if the provided number of rows and columns are not suited to create a matrix.
53    ///   For further information see [`MatPolyOverZ::new`].
54    pub fn sample_binomial(
55        num_rows: impl TryInto<i64> + Display,
56        num_cols: impl TryInto<i64> + Display,
57        max_degree: impl TryInto<i64> + Display,
58        n: impl Into<Z>,
59        p: impl Into<Q>,
60    ) -> Result<Self, MathError> {
61        Self::sample_binomial_with_offset(num_rows, num_cols, max_degree, 0, n, p)
62    }
63
64    /// Outputs a [`MatPolyOverZ`] instance with entries chosen according to the binomial
65    /// distribution parameterized by `n` and `p` with given `offset`.
66    ///
67    /// Parameters:
68    /// - `num_rows`: specifies the number of rows the new matrix should have
69    /// - `num_cols`: specifies the number of columns the new matrix should have
70    /// - `max_degree`: specifies the maximum length of all polynomials in the matrix,
71    ///   i.e. the maximum number of coefficients any polynomial in the matrix can have
72    /// - `offset`: specifies an offset applied to each sample
73    ///   collected from the binomial distribution
74    /// - `n`: specifies the number of trials
75    /// - `p`: specifies the probability of success
76    ///
77    /// Returns a new [`MatPolyOverZ`] instance with entries chosen
78    /// according to the binomial distribution or a [`MathError`]
79    /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`],
80    /// or the dimensions of the matrix were chosen too small.
81    ///
82    /// # Examples
83    /// ```
84    /// use qfall_math::integer::MatPolyOverZ;
85    ///
86    /// let sample = MatPolyOverZ::sample_binomial_with_offset(2, 2, 5, -1, 2, 0.5).unwrap();
87    /// ```
88    ///
89    /// # Errors and Failures
90    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
91    ///   if `n < 0` or `p ∉ (0,1)`.
92    /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
93    ///   if `n` does not fit into an [`i64`].
94    /// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
95    ///   the `max_degree` is negative or it does not fit into an [`i64`].
96    ///
97    /// # Panics ...
98    /// - if the provided number of rows and columns are not suited to create a matrix.
99    ///   For further information see [`MatPolyOverZ::new`].
100    pub fn sample_binomial_with_offset(
101        num_rows: impl TryInto<i64> + Display,
102        num_cols: impl TryInto<i64> + Display,
103        max_degree: impl TryInto<i64> + Display,
104        offset: impl Into<Z>,
105        n: impl Into<Z>,
106        p: impl Into<Q>,
107    ) -> Result<Self, MathError> {
108        let max_degree = evaluate_index(max_degree)?;
109        let offset: Z = offset.into();
110        let mut bin_sampler = BinomialSampler::init(n, p)?;
111        let mut matrix = MatPolyOverZ::new(num_rows, num_cols);
112
113        for row in 0..matrix.get_num_rows() {
114            for col in 0..matrix.get_num_columns() {
115                let mut poly_z = PolyOverZ::default();
116
117                for index in 0..=max_degree {
118                    let mut sample = bin_sampler.sample();
119                    sample += &offset;
120                    unsafe { poly_z.set_coeff_unchecked(index, sample) };
121                }
122
123                unsafe { matrix.set_entry_unchecked(row, col, poly_z) };
124            }
125        }
126
127        Ok(matrix)
128    }
129}
130
131#[cfg(test)]
132mod test_sample_binomial {
133    use super::{MatPolyOverZ, Q, Z};
134    use crate::traits::{GetCoefficient, MatrixDimensions, MatrixGetEntry};
135
136    // As all major tests regarding an appropriate binomial distribution,
137    // whether the correct interval is kept, and if the errors are thrown correctly,
138    // are performed in the `utils` module, we omit these tests here.
139
140    /// Checks whether the boundaries of the interval are kept.
141    #[test]
142    fn boundaries_kept() {
143        for _ in 0..8 {
144            let matrix = MatPolyOverZ::sample_binomial(1, 1, 0, 2, 0.5).unwrap();
145            let entry = matrix.get_entry(0, 0).unwrap();
146            let poly = entry.get_coeff(0).unwrap();
147
148            assert!(Z::ZERO <= poly);
149            assert!(poly <= 2);
150        }
151    }
152
153    /// Checks whether the number of coefficients is correct.
154    #[test]
155    fn nr_coeffs() {
156        let degrees = [1, 3, 7, 15, 32, 120];
157        for degree in degrees {
158            let matrix = MatPolyOverZ::sample_binomial(1, 1, degree, 256, 0.99999).unwrap();
159            let poly = matrix.get_entry(0, 0).unwrap();
160
161            assert_eq!(
162                degree,
163                poly.get_degree(),
164                "This test can fail with probability close to 0."
165            );
166        }
167    }
168
169    /// Checks whether matrices with at least one dimension chosen smaller than `1`
170    /// or too big for an [`i64`] results in an error.
171    #[should_panic]
172    #[test]
173    fn false_size() {
174        let _ = MatPolyOverZ::sample_binomial(0, 3, 0, 1, 0.5);
175    }
176
177    /// Checks whether providing a length smaller than `0` results in an error.
178    #[test]
179    fn invalid_max_degree() {
180        let res_0 = MatPolyOverZ::sample_binomial(1, 1, -1, 2, 0.5);
181        let res_1 = MatPolyOverZ::sample_binomial(1, 1, i64::MIN, 2, 0.5);
182
183        assert!(res_0.is_err());
184        assert!(res_1.is_err());
185    }
186
187    /// Checks whether `sample_binomial` is available for all types
188    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
189    /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
190    #[test]
191    fn availability() {
192        let _ = MatPolyOverZ::sample_binomial(1, 1, 0u8, 1u16, 7u8);
193        let _ = MatPolyOverZ::sample_binomial(1, 1, 0u16, 1u32, 7u16);
194        let _ = MatPolyOverZ::sample_binomial(1, 1, 0u32, 1u64, 7u32);
195        let _ = MatPolyOverZ::sample_binomial(1, 1, 0u64, 1i8, 7u64);
196        let _ = MatPolyOverZ::sample_binomial(1, 1, 0i8, 1i16, 7i8);
197        let _ = MatPolyOverZ::sample_binomial(1, 1, 0i16, 1i32, 7i16);
198        let _ = MatPolyOverZ::sample_binomial(1, 1, 0i32, 1i64, 7i32);
199        let _ = MatPolyOverZ::sample_binomial(1, 1, 0i64, Z::ONE, 7i64);
200        let _ = MatPolyOverZ::sample_binomial(1, 1, 0, 1u8, 0.5f32);
201        let _ = MatPolyOverZ::sample_binomial(1, 1, Z::ZERO, 1u8, 0.5f64);
202        let _ = MatPolyOverZ::sample_binomial(1, 1, 0, 1, Q::from((1, 2)));
203    }
204
205    /// Checks whether the size of uniformly random sampled matrices
206    /// fits the specified dimensions.
207    #[test]
208    fn matrix_size() {
209        let mat_0 = MatPolyOverZ::sample_binomial(3, 3, 0, 1, 0.5).unwrap();
210        let mat_1 = MatPolyOverZ::sample_binomial(4, 1, 0, 1, 0.5).unwrap();
211        let mat_2 = MatPolyOverZ::sample_binomial(1, 5, 0, 1, 0.5).unwrap();
212        let mat_3 = MatPolyOverZ::sample_binomial(15, 20, 0, 1, 0.5).unwrap();
213
214        assert_eq!(3, mat_0.get_num_rows());
215        assert_eq!(3, mat_0.get_num_columns());
216        assert_eq!(4, mat_1.get_num_rows());
217        assert_eq!(1, mat_1.get_num_columns());
218        assert_eq!(1, mat_2.get_num_rows());
219        assert_eq!(5, mat_2.get_num_columns());
220        assert_eq!(15, mat_3.get_num_rows());
221        assert_eq!(20, mat_3.get_num_columns());
222    }
223}
224
225#[cfg(test)]
226mod test_sample_binomial_with_offset {
227    use super::{MatPolyOverZ, Q, Z};
228    use crate::traits::{GetCoefficient, MatrixDimensions, MatrixGetEntry};
229
230    // As all major tests regarding an appropriate binomial distribution,
231    // whether the correct interval is kept, and if the errors are thrown correctly,
232    // are performed in the `utils` module, we omit these tests here.
233
234    /// Checks whether the boundaries of the interval are kept.
235    #[test]
236    fn boundaries_kept() {
237        for _ in 0..8 {
238            let matrix = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0, -1, 2, 0.5).unwrap();
239            let entry = matrix.get_entry(0, 0).unwrap();
240            let poly = entry.get_coeff(0).unwrap();
241
242            assert!(Z::MINUS_ONE <= poly);
243            assert!(poly <= Z::ONE);
244        }
245    }
246
247    /// Checks whether the number of coefficients is correct.
248    #[test]
249    fn nr_coeffs() {
250        let degrees = [1, 3, 7, 15, 32, 120];
251        for degree in degrees {
252            let matrix =
253                MatPolyOverZ::sample_binomial_with_offset(1, 1, degree, -1, 256, 0.99999).unwrap();
254            let poly = matrix.get_entry(0, 0).unwrap();
255
256            assert_eq!(
257                degree,
258                poly.get_degree(),
259                "This test can fail with probability close to 0."
260            );
261        }
262    }
263
264    /// Checks whether matrices with at least one dimension chosen smaller than `1`
265    /// or too big for an [`i64`] results in an error.
266    #[should_panic]
267    #[test]
268    fn false_size() {
269        let _ = MatPolyOverZ::sample_binomial_with_offset(0, 3, 0, 0, 1, 0.5);
270    }
271
272    /// Checks whether providing a length smaller than `0` results in an error.
273    #[test]
274    fn invalid_max_degree() {
275        let res_0 = MatPolyOverZ::sample_binomial_with_offset(1, 1, -1, -1, 2, 0.5);
276        let res_1 = MatPolyOverZ::sample_binomial_with_offset(1, 1, i64::MIN, -1, 2, 0.5);
277
278        assert!(res_0.is_err());
279        assert!(res_1.is_err());
280    }
281
282    /// Checks whether `sample_binomial_with_offset` is available for all types
283    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
284    /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
285    #[test]
286    fn availability() {
287        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0u8, -1, 1u16, 7u8);
288        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0u16, 0, 1u32, 7u16);
289        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0u32, Z::ONE, 1u64, 7u32);
290        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0u64, Z::MINUS_ONE, 1i8, 7u64);
291        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0i8, -1, 1i16, 7i8);
292        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0i16, -1, 1i32, 7i16);
293        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0i32, -1, 1i64, 7i32);
294        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0i64, -1, Z::ONE, 7i64);
295        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0, -1, 1u8, 0.5f32);
296        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, Z::ZERO, -1, 1u8, 0.5f64);
297        let _ = MatPolyOverZ::sample_binomial_with_offset(1, 1, 0, -1, 1, Q::from((1, 2)));
298    }
299
300    /// Checks whether the size of uniformly random sampled matrices
301    /// fits the specified dimensions.
302    #[test]
303    fn matrix_size() {
304        let mat_0 = MatPolyOverZ::sample_binomial_with_offset(3, 3, 0, -1, 1, 0.5).unwrap();
305        let mat_1 = MatPolyOverZ::sample_binomial_with_offset(4, 1, 0, -1, 1, 0.5).unwrap();
306        let mat_2 = MatPolyOverZ::sample_binomial_with_offset(1, 5, 0, -1, 1, 0.5).unwrap();
307        let mat_3 = MatPolyOverZ::sample_binomial_with_offset(15, 20, 0, -1, 1, 0.5).unwrap();
308
309        assert_eq!(3, mat_0.get_num_rows());
310        assert_eq!(3, mat_0.get_num_columns());
311        assert_eq!(4, mat_1.get_num_rows());
312        assert_eq!(1, mat_1.get_num_columns());
313        assert_eq!(1, mat_2.get_num_rows());
314        assert_eq!(5, mat_2.get_num_columns());
315        assert_eq!(15, mat_3.get_num_rows());
316        assert_eq!(20, mat_3.get_num_columns());
317    }
318}
qfall_math/integer/mat_poly_over_z/sample/binomial.rs

qfall_math/integer/mat_poly_over_z/sample/
binomial.rs
