qfall_math/rational/mat_q/
rounding.rs

1// Copyright © 2024 Marvin Beckmann
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 includes functionality for rounding instances of [`MatQ`] entrywise.
10
11use super::MatQ;
12use crate::{
13    error::MathError,
14    integer::MatZ,
15    rational::Q,
16    traits::{MatrixDimensions, MatrixGetEntry, MatrixSetEntry},
17};
18
19impl MatQ {
20    /// Rounds all entries of the given rational matrix [`MatQ`] down to the next integer
21    /// as a [`MatZ`].
22    ///
23    /// # Examples
24    /// ```
25    /// use qfall_math::rational::MatQ;
26    /// use qfall_math::integer::MatZ;
27    /// use std::str::FromStr;
28    ///
29    /// let value = MatQ::from_str("[[5/2, 1]]").unwrap();
30    /// assert_eq!(MatZ::from_str("[[2, 1]]").unwrap(), value.floor());
31    ///
32    /// let value = MatQ::from_str("[[-5/2, 1]]").unwrap();
33    /// assert_eq!(MatZ::from_str("[[-3, 1]]").unwrap(), value.floor());
34    /// ```
35    pub fn floor(&self) -> MatZ {
36        let mut out = MatZ::new(self.get_num_rows(), self.get_num_columns());
37        for i in 0..out.get_num_rows() {
38            for j in 0..out.get_num_columns() {
39                let entry = unsafe { self.get_entry_unchecked(i, j) }.floor();
40                unsafe { out.set_entry_unchecked(i, j, entry) };
41            }
42        }
43        out
44    }
45
46    /// Rounds all entries of the given rational matrix [`MatQ`] up to the next integer
47    /// as a [`MatZ`].
48    ///
49    /// # Examples
50    /// ```
51    /// use qfall_math::rational::MatQ;
52    /// use qfall_math::integer::MatZ;
53    /// use std::str::FromStr;
54    ///
55    /// let value = MatQ::from_str("[[5/2, 1]]").unwrap();
56    /// assert_eq!(MatZ::from_str("[[3, 1]]").unwrap(), value.ceil());
57    ///
58    /// let value = MatQ::from_str("[[-5/2, 1]]").unwrap();
59    /// assert_eq!(MatZ::from_str("[[-2, 1]]").unwrap(), value.ceil());
60    /// ```
61    pub fn ceil(&self) -> MatZ {
62        let mut out = MatZ::new(self.get_num_rows(), self.get_num_columns());
63        for i in 0..out.get_num_rows() {
64            for j in 0..out.get_num_columns() {
65                let entry = unsafe { self.get_entry_unchecked(i, j) }.ceil();
66                unsafe { out.set_entry_unchecked(i, j, entry) };
67            }
68        }
69        out
70    }
71
72    /// Rounds all entries of the given rational matrix [`MatQ`] to the closest integer
73    /// as a [`MatZ`].
74    ///
75    /// # Examples
76    /// ```
77    /// use qfall_math::rational::MatQ;
78    /// use qfall_math::integer::MatZ;
79    /// use std::str::FromStr;
80    ///
81    /// let value = MatQ::from_str("[[5/2, 1]]").unwrap();
82    /// assert_eq!(MatZ::from_str("[[3, 1]]").unwrap(), value.round());
83    ///
84    /// let value = MatQ::from_str("[[-5/2, 1]]").unwrap();
85    /// assert_eq!(MatZ::from_str("[[-2, 1]]").unwrap(), value.round());
86    /// ```
87    pub fn round(&self) -> MatZ {
88        let mut out = MatZ::new(self.get_num_rows(), self.get_num_columns());
89        for i in 0..out.get_num_rows() {
90            for j in 0..out.get_num_columns() {
91                let entry = unsafe { self.get_entry_unchecked(i, j) }.round();
92                unsafe { out.set_entry_unchecked(i, j, entry) };
93            }
94        }
95        out
96    }
97
98    /// Returns a matrix, where each entry was simplified using [`Q::simplify`],
99    /// i.e. each entry becomes the smallest rational with the smallest denominator in the range
100    /// `\[entry - |precision|, entry + |precision|\]`.
101    ///
102    /// This function allows to free memory in exchange for the specified loss of
103    /// precision (see Example 3). Be aware that this loss of precision is propagated by
104    /// arithmetic operations depending on the size of the matrices.
105    /// This functions allows to trade precision for efficiency.
106    ///
107    /// This function ensures that simplifying does not change the sign of any entry in the matrix.
108    ///
109    /// Parameters:
110    /// - `precision`: the precision the new entries can differ from `self`.
111    ///   Note that the absolute value is relevant, not the sign.
112    ///
113    /// Returns a new [`MatQ`] with each entry being the simplest fraction within the defined range.
114    ///
115    /// # Examples
116    /// ```
117    /// use qfall_math::rational::{MatQ, Q};
118    /// use qfall_math::traits::{MatrixGetEntry, MatrixSetEntry};
119    /// let mut matrix = MatQ::new(1, 2);
120    /// matrix.set_entry(0, 0, Q::from((17, 20))).unwrap();
121    /// let precision = Q::from((1, 20));
122    ///
123    /// let matrix_simplified = matrix.simplify(precision);
124    ///
125    /// assert_eq!(Q::from((4, 5)), matrix_simplified.get_entry(0, 0).unwrap());
126    /// ```
127    ///
128    /// ```
129    /// use qfall_math::rational::{MatQ, Q};
130    /// use qfall_math::traits::{MatrixGetEntry, MatrixSetEntry};
131    /// let mut matrix = MatQ::new(2, 1);
132    /// matrix.set_entry(0, 0, Q::from((3, 2))).unwrap();
133    ///
134    /// let mat_simplified = matrix.simplify(0.5);
135    ///
136    /// assert_eq!(Q::ONE, mat_simplified.get_entry(0, 0).unwrap());
137    /// ```
138    ///
139    /// ## Simplify with reasonable precision loss
140    /// This example uses [`Q::INV_MAX32`], i.e. a loss of precision of at most `1 / 2^31 - 2` behind the decimal point.
141    /// If you require higher precision, [`Q::INV_MAX62`] is available.
142    /// ```
143    /// use qfall_math::rational::{MatQ, Q};
144    /// use qfall_math::traits::{MatrixGetEntry, MatrixSetEntry};
145    /// let mut matrix = MatQ::new(1, 1);
146    /// matrix.set_entry(0, 0, Q::PI).unwrap();
147    ///
148    /// let mat_simplified = matrix.simplify(Q::INV_MAX32);
149    ///
150    /// let entry_simplified = mat_simplified.get_entry(0, 0).unwrap();
151    ///
152    /// assert_ne!(&Q::PI, &entry_simplified);
153    /// assert!(&entry_simplified >= &(Q::PI - Q::INV_MAX32));
154    /// assert!(&entry_simplified <= &(Q::PI + Q::INV_MAX32));
155    /// ```
156    pub fn simplify(&self, precision: impl Into<Q>) -> MatQ {
157        let precision = precision.into();
158        let mut out = MatQ::new(self.get_num_rows(), self.get_num_columns());
159
160        for i in 0..self.get_num_rows() {
161            for j in 0..self.get_num_columns() {
162                let entry = unsafe { self.get_entry_unchecked(i, j) };
163                let simplified_entry = entry.simplify(&precision);
164                unsafe { out.set_entry_unchecked(i, j, simplified_entry) };
165            }
166        }
167
168        out
169    }
170
171    /// Performs the randomized rounding algorithm entrywise
172    /// by sampling from a discrete Gaussian over the integers shifted
173    /// by `self` with gaussian parameter `r`.
174    ///
175    /// Parameters:
176    /// - `r`: specifies the Gaussian parameter, which is proportional
177    ///   to the standard deviation `sigma * sqrt(2 * pi) = r`
178    ///
179    /// Returns the rounded matrix as a [`MatZ`] or an error if `r < 0`.
180    ///
181    /// # Examples
182    /// ```
183    /// use qfall_math::rational::MatQ;
184    /// use std::str::FromStr;
185    ///
186    /// let value = MatQ::from_str("[[5/2, 1]]").unwrap();
187    /// let rounded = value.randomized_rounding(3).unwrap();
188    /// ```
189    ///
190    /// # Errors and Failures
191    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
192    ///   if `r < 0`.
193    ///
194    /// This function implements randomized rounding according to:
195    /// - \[1\] Peikert, C. (2010, August).
196    ///   An efficient and parallel Gaussian sampler for lattices.
197    ///   In: Annual Cryptology Conference (pp. 80-97).
198    ///   <https://link.springer.com/chapter/10.1007/978-3-642-14623-7_5>
199    pub fn randomized_rounding(&self, r: impl Into<Q>) -> Result<MatZ, MathError> {
200        let mut out = MatZ::new(self.get_num_rows(), self.get_num_columns());
201        let r = r.into();
202        for i in 0..out.get_num_rows() {
203            for j in 0..out.get_num_columns() {
204                let entry = unsafe { self.get_entry_unchecked(i, j) }.randomized_rounding(&r)?;
205                unsafe { out.set_entry_unchecked(i, j, entry) };
206            }
207        }
208        Ok(out)
209    }
210}
211
212#[cfg(test)]
213mod test_floor {
214    use crate::{integer::MatZ, rational::MatQ};
215    use std::str::FromStr;
216
217    // Ensure that positive rationals are rounded correctly
218    #[test]
219    fn positive() {
220        let value = MatQ::from_str(&format!("[[1/{}, {}/2]]", u64::MAX, i64::MAX)).unwrap();
221        let cmp = MatZ::from_str(&format!("[[0, {}]]", (i64::MAX - 1) / 2)).unwrap();
222
223        assert_eq!(cmp, value.floor());
224    }
225
226    // Ensure that negative rationals are rounded correctly
227    #[test]
228    fn negative() {
229        let value = MatQ::from_str(&format!("[[-1/{}, -{}/2]]", u64::MAX, i64::MAX)).unwrap();
230        let cmp = MatZ::from_str(&format!("[[-1, {}]]", (-i64::MAX - 1) / 2)).unwrap();
231
232        assert_eq!(cmp, value.floor());
233    }
234}
235
236#[cfg(test)]
237mod test_ceil {
238    use crate::{integer::MatZ, rational::MatQ};
239    use std::str::FromStr;
240
241    // Ensure that positive rationals are rounded correctly
242    #[test]
243    fn positive() {
244        let value = MatQ::from_str(&format!("[[1/{}, {}/2]]", u64::MAX, i64::MAX)).unwrap();
245        let cmp = MatZ::from_str(&format!("[[1, {}]]", (i64::MAX - 1) / 2 + 1)).unwrap();
246
247        assert_eq!(cmp, value.ceil());
248    }
249
250    // Ensure that negative rationals are rounded correctly
251    #[test]
252    fn negative() {
253        let value = MatQ::from_str(&format!("[[-1/{}, -{}/2]]", u64::MAX, i64::MAX)).unwrap();
254        let cmp = MatZ::from_str(&format!("[[0, {}]]", (-i64::MAX - 1) / 2 + 1)).unwrap();
255
256        assert_eq!(cmp, value.ceil());
257    }
258}
259
260#[cfg(test)]
261mod test_round {
262    use crate::{integer::MatZ, rational::MatQ};
263    use std::str::FromStr;
264
265    // Ensure that positive rationals are rounded correctly
266    #[test]
267    fn positive() {
268        let value = MatQ::from_str(&format!("[[1/{}, {}/2]]", u64::MAX, i64::MAX)).unwrap();
269        let cmp = MatZ::from_str(&format!("[[0, {}]]", (i64::MAX - 1) / 2 + 1)).unwrap();
270
271        assert_eq!(cmp, value.round());
272    }
273
274    // Ensure that negative rationals are rounded correctly
275    #[test]
276    fn negative() {
277        let value = MatQ::from_str(&format!("[[-1/{}, -{}/2]]", u64::MAX, i64::MAX)).unwrap();
278        let cmp = MatZ::from_str(&format!("[[0, {}]]", (-i64::MAX - 1) / 2 + 1)).unwrap();
279
280        assert_eq!(cmp, value.round());
281    }
282}
283
284#[cfg(test)]
285mod test_randomized_rounding {
286    use crate::rational::MatQ;
287    use std::str::FromStr;
288
289    /// Ensure that a `r < 0` throws an error
290    #[test]
291    fn negative_r() {
292        let value = MatQ::from_str("[[5/2, 1]]").unwrap();
293        assert!(value.randomized_rounding(-1).is_err());
294    }
295}
qfall_math/rational/mat_q/rounding.rs

qfall_math/rational/mat_q/
rounding.rs
