qfall_math/rational/poly_over_q/rounding.rs
1// Copyright © 2024 Marcel Luca Schmidt
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 [`PolyOverQ`] coefficient-wise.
10
11use super::PolyOverQ;
12use crate::{
13 error::MathError,
14 integer::PolyOverZ,
15 rational::Q,
16 traits::{GetCoefficient, SetCoefficient},
17};
18
19impl PolyOverQ {
20 /// Rounds all coefficients of the given rational polynomial [`PolyOverQ`] down to the next integer
21 /// as a [`PolyOverZ`].
22 ///
23 /// # Examples
24 /// ```
25 /// use qfall_math::rational::PolyOverQ;
26 /// use qfall_math::integer::PolyOverZ;
27 /// use std::str::FromStr;
28 ///
29 /// let value = PolyOverQ::from_str("2 5/2 1").unwrap();
30 /// assert_eq!(PolyOverZ::from_str("2 2 1").unwrap(), value.floor());
31 ///
32 /// let value = PolyOverQ::from_str("2 -5/2 1").unwrap();
33 /// assert_eq!(PolyOverZ::from_str("2 -3 1").unwrap(), value.floor());
34 /// ```
35 pub fn floor(&self) -> PolyOverZ {
36 let mut out = PolyOverZ::from(unsafe { self.get_coeff_unchecked(0).floor() });
37 for i in 1..self.get_degree() + 1 {
38 let coeff = unsafe { self.get_coeff_unchecked(i).floor() };
39 unsafe { out.set_coeff_unchecked(i, coeff) };
40 }
41
42 out
43 }
44
45 /// Rounds all coefficients of the given rational polynomial [`PolyOverQ`] up to the next integer
46 /// as a [`PolyOverZ`].
47 ///
48 /// # Examples
49 /// ```
50 /// use qfall_math::rational::PolyOverQ;
51 /// use qfall_math::integer::PolyOverZ;
52 /// use std::str::FromStr;
53 ///
54 /// let value = PolyOverQ::from_str("2 5/2 1").unwrap();
55 /// assert_eq!(PolyOverZ::from_str("2 3 1").unwrap(), value.ceil());
56 ///
57 /// let value = PolyOverQ::from_str("2 -5/2 1").unwrap();
58 /// assert_eq!(PolyOverZ::from_str("2 -2 1").unwrap(), value.ceil());
59 /// ```
60 pub fn ceil(&self) -> PolyOverZ {
61 let mut out = PolyOverZ::from(unsafe { self.get_coeff_unchecked(0).ceil() });
62 for i in 1..self.get_degree() + 1 {
63 let coeff = unsafe { self.get_coeff_unchecked(i).ceil() };
64 unsafe { out.set_coeff_unchecked(i, coeff) };
65 }
66
67 out
68 }
69
70 /// Rounds all coefficients of the given rational polynomial [`PolyOverQ`] to the closest integer
71 /// as a [`PolyOverZ`].
72 ///
73 /// # Examples
74 /// ```
75 /// use qfall_math::rational::PolyOverQ;
76 /// use qfall_math::integer::PolyOverZ;
77 /// use std::str::FromStr;
78 ///
79 /// let value = PolyOverQ::from_str("2 5/2 1").unwrap();
80 /// assert_eq!(PolyOverZ::from_str("2 3 1").unwrap(), value.round());
81 ///
82 /// let value = PolyOverQ::from_str("2 -5/2 1").unwrap();
83 /// assert_eq!(PolyOverZ::from_str("2 -2 1").unwrap(), value.round());
84 /// ```
85 pub fn round(&self) -> PolyOverZ {
86 let mut out = PolyOverZ::from(unsafe { self.get_coeff_unchecked(0).round() });
87
88 for i in 1..self.get_degree() + 1 {
89 let coeff = unsafe { self.get_coeff_unchecked(i).round() };
90 unsafe { out.set_coeff_unchecked(i, coeff) };
91 }
92
93 out
94 }
95
96 /// Performs the randomized rounding algorithm coefficient-wise
97 /// by sampling from a discrete Gaussian over the integers shifted
98 /// by `self` with gaussian parameter `r`.
99 ///
100 /// Parameters:
101 /// - `r`: specifies the Gaussian parameter, which is proportional
102 /// to the standard deviation `sigma * sqrt(2 * pi) = r`
103 ///
104 /// Returns the rounded polynomial as a [`PolyOverZ`] or an error if `r < 0`.
105 ///
106 /// # Examples
107 /// ```
108 /// use qfall_math::rational::PolyOverQ;
109 /// use std::str::FromStr;
110 ///
111 /// let value = PolyOverQ::from_str("2 5/2 1").unwrap();
112 /// let rounded = value.randomized_rounding(3).unwrap();
113 /// ```
114 ///
115 /// # Errors and Failures
116 /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
117 /// if `r < 0`.
118 ///
119 /// This function implements randomized rounding according to:
120 /// - \[1\] Peikert, C. (2010, August).
121 /// An efficient and parallel Gaussian sampler for lattices.
122 /// In: Annual Cryptology Conference (pp. 80-97).
123 /// <https://link.springer.com/chapter/10.1007/978-3-642-14623-7_5>
124 pub fn randomized_rounding(&self, r: impl Into<Q>) -> Result<PolyOverZ, MathError> {
125 let r = r.into();
126 let mut out =
127 PolyOverZ::from(unsafe { self.get_coeff_unchecked(0).randomized_rounding(&r)? });
128 for i in 1..self.get_degree() + 1 {
129 let coeff = unsafe { self.get_coeff_unchecked(i).randomized_rounding(&r)? };
130 unsafe { out.set_coeff_unchecked(i, coeff) };
131 }
132
133 Ok(out)
134 }
135}
136
137#[cfg(test)]
138mod test_floor {
139 use crate::{integer::PolyOverZ, rational::PolyOverQ};
140 use std::str::FromStr;
141
142 // Ensure that positive rationals are rounded correctly
143 #[test]
144 fn positive() {
145 let value = PolyOverQ::from_str(&format!("2 1/{} {}/2", u64::MAX, i64::MAX)).unwrap();
146 let cmp = PolyOverZ::from_str(&format!("2 0 {}", (i64::MAX - 1) / 2)).unwrap();
147
148 assert_eq!(cmp, value.floor());
149 }
150
151 // Ensure that negative rationals are rounded correctly
152 #[test]
153 fn negative() {
154 let value = PolyOverQ::from_str(&format!("2 -1/{} -{}/2", u64::MAX, i64::MAX)).unwrap();
155 let cmp = PolyOverZ::from_str(&format!("2 -1 {}", (-i64::MAX - 1) / 2)).unwrap();
156
157 assert_eq!(cmp, value.floor());
158 }
159}
160
161#[cfg(test)]
162mod test_ceil {
163 use crate::{integer::PolyOverZ, rational::PolyOverQ};
164 use std::str::FromStr;
165
166 // Ensure that positive rationals are rounded correctly
167 #[test]
168 fn positive() {
169 let value = PolyOverQ::from_str(&format!("2 1/{} {}/2", u64::MAX, i64::MAX)).unwrap();
170 let cmp = PolyOverZ::from_str(&format!("2 1 {}", (i64::MAX - 1) / 2 + 1)).unwrap();
171
172 assert_eq!(cmp, value.ceil());
173 }
174
175 // Ensure that negative rationals are rounded correctly
176 #[test]
177 fn negative() {
178 let value = PolyOverQ::from_str(&format!("2 -1/{} -{}/2", u64::MAX, i64::MAX)).unwrap();
179 let cmp = PolyOverZ::from_str(&format!("2 0 {}", (-i64::MAX - 1) / 2 + 1)).unwrap();
180
181 assert_eq!(cmp, value.ceil());
182 }
183}
184
185#[cfg(test)]
186mod test_round {
187 use crate::{integer::PolyOverZ, rational::PolyOverQ};
188 use std::str::FromStr;
189
190 // Ensure that positive rationals are rounded correctly
191 #[test]
192 fn positive() {
193 let value = PolyOverQ::from_str(&format!("2 1/{} {}/2", u64::MAX, i64::MAX)).unwrap();
194 let cmp = PolyOverZ::from_str(&format!("2 0 {}", (i64::MAX - 1) / 2 + 1)).unwrap();
195
196 assert_eq!(cmp, value.round());
197 }
198
199 // Ensure that negative rationals are rounded correctly
200 #[test]
201 fn negative() {
202 let value = PolyOverQ::from_str(&format!("2 -1/{} -{}/2", u64::MAX, i64::MAX)).unwrap();
203 let cmp = PolyOverZ::from_str(&format!("2 0 {}", (-i64::MAX - 1) / 2 + 1)).unwrap();
204
205 assert_eq!(cmp, value.round());
206 }
207}
208
209#[cfg(test)]
210mod test_randomized_rounding {
211 use crate::rational::PolyOverQ;
212 use std::str::FromStr;
213
214 /// Ensure that a `r < 0` throws an error
215 #[test]
216 fn negative_r() {
217 let value = PolyOverQ::from_str("2 5/2 1").unwrap();
218 assert!(value.randomized_rounding(-1).is_err());
219 }
220}