qfall_math/integer/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 according to the binomial distribution.
10
11use crate::{
12    error::MathError,
13    integer::{PolyOverZ, Z},
14    rational::Q,
15    traits::SetCoefficient,
16    utils::{index::evaluate_index, sample::binomial::BinomialSampler},
17};
18use std::fmt::Display;
19
20impl PolyOverZ {
21    /// Generates a [`PolyOverZ`] instance of maximum degree `max_degree` and
22    /// coefficients chosen according to the binomial distribution
23    /// parameterized by `n` and `p`.
24    ///
25    /// Parameters:
26    /// - `max_degree`: specifies the length of the polynomial,
27    ///   i.e. the number of coefficients
28    /// - `n`: specifies the number of trials
29    /// - `p`: specifies the probability of success
30    ///
31    /// Returns a fresh [`PolyOverZ`] instance with each value sampled
32    /// according to the binomial distribution or a [`MathError`]
33    /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`],
34    /// or `max_degree` is negative or does not into an [`i64`].
35    ///
36    /// # Examples
37    /// ```
38    /// use qfall_math::integer::PolyOverZ;
39    ///
40    /// let sample = PolyOverZ::sample_binomial(2, 2, 0.5).unwrap();
41    /// ```
42    ///
43    /// # Errors and Failures
44    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
45    ///   if `n < 0`.
46    /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
47    ///   if `p ∉ (0,1)`.
48    /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
49    ///   if `n` does not fit into an [`i64`].
50    /// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
51    ///   the `max_degree` is negative or it does not fit into an [`i64`].
52    pub fn sample_binomial(
53        max_degree: impl TryInto<i64> + Display,
54        n: impl Into<Z>,
55        p: impl Into<Q>,
56    ) -> Result<Self, MathError> {
57        Self::sample_binomial_with_offset(max_degree, 0, n, p)
58    }
59
60    /// Generates a [`PolyOverZ`] instance of maximum degree `max_degree` and
61    /// coefficients chosen according to the binomial distribution
62    /// parameterized by `n` and `p` with given `offset`.
63    ///
64    /// Parameters:
65    /// - `max_degree`: specifies the length of the polynomial,
66    ///   i.e. the number of coefficients
67    /// - `offset`: specifies an offset applied to each sample
68    ///   collected from the binomial distribution
69    /// - `n`: specifies the number of trials
70    /// - `p`: specifies the probability of success
71    ///
72    /// Returns a fresh [`PolyOverZ`] instance with each value sampled
73    /// according to the binomial distribution or a [`MathError`]
74    /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`],
75    /// or `max_degree` is negative or does not into an [`i64`].
76    ///
77    /// # Examples
78    /// ```
79    /// use qfall_math::integer::PolyOverZ;
80    ///
81    /// let sample = PolyOverZ::sample_binomial_with_offset(2, -1, 2, 0.5).unwrap();
82    /// ```
83    ///
84    /// # Errors and Failures
85    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
86    ///   if `n < 0`.
87    /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
88    ///   if `p ∉ (0,1)`.
89    /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
90    ///   if `n` does not fit into an [`i64`].
91    /// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
92    ///   the `max_degree` is negative or it does not fit into an [`i64`].
93    pub fn sample_binomial_with_offset(
94        max_degree: impl TryInto<i64> + Display,
95        offset: impl Into<Z>,
96        n: impl Into<Z>,
97        p: impl Into<Q>,
98    ) -> Result<Self, MathError> {
99        let max_degree = evaluate_index(max_degree)?;
100        let offset: Z = offset.into();
101
102        let mut poly_z = PolyOverZ::default();
103
104        let mut bin_sampler = BinomialSampler::init(n, p)?;
105
106        for index in 0..=max_degree {
107            let mut sample = bin_sampler.sample();
108            sample += &offset;
109            unsafe { poly_z.set_coeff_unchecked(index, sample) };
110        }
111
112        Ok(poly_z)
113    }
114}
115
116#[cfg(test)]
117mod test_sample_binomial {
118    use super::{PolyOverZ, Q, Z};
119    use crate::traits::GetCoefficient;
120
121    // As all major tests regarding an appropriate binomial distribution,
122    // whether the correct interval is kept, and if the errors are thrown correctly,
123    // are performed in the `utils` module, we omit these tests here.
124
125    /// Checks whether the boundaries of the interval are kept.
126    #[test]
127    fn boundaries_kept() {
128        for _ in 0..8 {
129            let poly = PolyOverZ::sample_binomial(0, 2, 0.5).unwrap();
130            let sample = poly.get_coeff(0).unwrap();
131            assert!(Z::ZERO <= sample);
132            assert!(sample <= 2);
133        }
134    }
135
136    /// Checks whether the number of coefficients is correct.
137    #[test]
138    fn nr_coeffs() {
139        let degrees = [1, 3, 7, 15, 32, 120];
140        for degree in degrees {
141            let res = PolyOverZ::sample_binomial(degree, 256, 0.99999).unwrap();
142
143            assert_eq!(
144                degree,
145                res.get_degree(),
146                "This test can fail with probability close to 0."
147            );
148        }
149    }
150
151    /// Checks whether providing a length smaller than `0` results in an error.
152    #[test]
153    fn invalid_max_degree() {
154        let res_0 = PolyOverZ::sample_binomial(-1, 2, 0.5);
155        let res_1 = PolyOverZ::sample_binomial(i64::MIN, 2, 0.5);
156
157        assert!(res_0.is_err());
158        assert!(res_1.is_err());
159    }
160
161    /// Checks whether `sample_binomial` is available for all types
162    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
163    /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
164    #[test]
165    fn availability() {
166        let _ = PolyOverZ::sample_binomial(1, 1u16, 7u8);
167        let _ = PolyOverZ::sample_binomial(1, 1u32, 7u16);
168        let _ = PolyOverZ::sample_binomial(1, 1u64, 7u32);
169        let _ = PolyOverZ::sample_binomial(1, 1i8, 7u64);
170        let _ = PolyOverZ::sample_binomial(1, 1i16, 7i8);
171        let _ = PolyOverZ::sample_binomial(1, 1i32, 7i16);
172        let _ = PolyOverZ::sample_binomial(1, 1i64, 7i32);
173        let _ = PolyOverZ::sample_binomial(1, Z::ONE, 7i64);
174        let _ = PolyOverZ::sample_binomial(1, 1u8, 0.5f32);
175        let _ = PolyOverZ::sample_binomial(1, 1u8, 0.5f64);
176        let _ = PolyOverZ::sample_binomial(1, 1, Q::from((1, 2)));
177    }
178}
179
180#[cfg(test)]
181mod test_sample_binomial_with_offset {
182    use super::{PolyOverZ, Q, Z};
183    use crate::traits::GetCoefficient;
184
185    // As all major tests regarding an appropriate binomial distribution,
186    // whether the correct interval is kept, and if the errors are thrown correctly,
187    // are performed in the `utils` module, we omit these tests here.
188
189    /// Checks whether the boundaries of the interval are kept.
190    #[test]
191    fn boundaries_kept() {
192        for _ in 0..8 {
193            let poly = PolyOverZ::sample_binomial_with_offset(0, -1, 2, 0.5).unwrap();
194            let sample = poly.get_coeff(0).unwrap();
195            assert!(Z::MINUS_ONE <= sample);
196            assert!(sample <= Z::ONE);
197        }
198    }
199
200    /// Checks whether the number of coefficients is correct.
201    #[test]
202    fn nr_coeffs() {
203        let degrees = [1, 3, 7, 15, 32, 120];
204        for degree in degrees {
205            let res = PolyOverZ::sample_binomial_with_offset(degree, 1, 2, 0.5).unwrap();
206
207            assert_eq!(degree, res.get_degree());
208        }
209    }
210
211    /// Checks whether providing a length smaller than `0` results in an error.
212    #[test]
213    fn invalid_max_degree() {
214        let res_0 = PolyOverZ::sample_binomial_with_offset(-1, -1, 2, 0.5);
215        let res_1 = PolyOverZ::sample_binomial_with_offset(i64::MIN, -1, 2, 0.5);
216
217        assert!(res_0.is_err());
218        assert!(res_1.is_err());
219    }
220
221    /// Checks whether `sample_binomial_with_offset` is available for all types
222    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
223    /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
224    #[test]
225    fn availability() {
226        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1u16, 7u8);
227        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1u32, 7u16);
228        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1u64, 7u32);
229        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1i8, 7u64);
230        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1i16, 7i8);
231        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1i32, 7i16);
232        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1i64, 7i32);
233        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, Z::ONE, 7i64);
234        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1u8, 0.5f32);
235        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1u8, 0.5f64);
236        let _ = PolyOverZ::sample_binomial_with_offset(1, 0, 1, Q::from((1, 2)));
237    }
238}
qfall_math/integer/poly_over_z/sample/binomial.rs

qfall_math/integer/poly_over_z/sample/
binomial.rs
