qfall_math/integer_mod_q/mat_zq/vector/norm.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 includes functionality to compute several norms
10//! defined on vectors.
11
12use super::super::MatZq;
13use crate::{
14 error::MathError, integer::Z, integer_mod_q::fmpz_mod_helpers::length, rational::Q,
15 traits::MatrixDimensions,
16};
17use flint_sys::fmpz::fmpz_addmul;
18
19impl MatZq {
20 /// Returns the squared Euclidean norm or squared 2-norm of the given (row or column) vector
21 /// or an error if the given matrix is not a vector.
22 ///
23 /// Each length of an entry is defined as the shortest distance
24 /// to the next zero instance in the ring.
25 ///
26 /// # Examples
27 /// ```
28 /// use qfall_math::{
29 /// integer::Z,
30 /// integer_mod_q::MatZq,
31 /// };
32 /// use std::str::FromStr;
33 ///
34 /// let vec = MatZq::from_str("[[1],[2],[3]] mod 4").unwrap();
35 ///
36 /// let sqrd_2_norm = vec.norm_eucl_sqrd().unwrap();
37 ///
38 /// // 1*1 + 2*2 + 1*1 = 6
39 /// assert_eq!(Z::from(6), sqrd_2_norm);
40 /// ```
41 ///
42 /// # Errors and Failures
43 /// - Returns a [`MathError`] of type [`MathError::VectorFunctionCalledOnNonVector`] if
44 /// the given [`MatZq`] instance is not a (row or column) vector.
45 pub fn norm_eucl_sqrd(&self) -> Result<Z, MathError> {
46 if !self.is_vector() {
47 return Err(MathError::VectorFunctionCalledOnNonVector(
48 String::from("norm_eucl_sqrd"),
49 self.get_num_rows(),
50 self.get_num_columns(),
51 ));
52 }
53
54 // compute lengths of all entries in matrix with regards to modulus
55 let entry_lengths = self.collect_lengths();
56
57 // sum squared entries in result
58 let mut result = Z::ZERO;
59 for entry in entry_lengths {
60 // sets result = result + entry * entry without cloned Z element
61 unsafe { fmpz_addmul(&mut result.value, &entry.value, &entry.value) }
62 }
63
64 Ok(result)
65 }
66
67 /// Returns the Euclidean norm or 2-norm of the given (row or column) vector
68 /// or an error if the given matrix is not a vector.
69 ///
70 /// Each length of an entry is defined as the shortest distance
71 /// to the next zero instance in the ring.
72 ///
73 /// # Examples
74 /// ```
75 /// use qfall_math::{
76 /// rational::Q,
77 /// integer_mod_q::MatZq,
78 /// };
79 /// use std::str::FromStr;
80 ///
81 /// let vec = MatZq::from_str("[[2],[2],[2],[2]] mod 4").unwrap();
82 ///
83 /// let eucl_norm = vec.norm_eucl().unwrap();
84 ///
85 /// // sqrt(4 * 2^2) = 4
86 /// assert_eq!(Q::from(4), eucl_norm);
87 /// ```
88 ///
89 /// # Errors and Failures
90 /// - Returns a [`MathError`] of type [`MathError::VectorFunctionCalledOnNonVector`] if
91 /// the given [`MatZq`] instance is not a (row or column) vector.
92 pub fn norm_eucl(&self) -> Result<Q, MathError> {
93 Ok(self.norm_eucl_sqrd()?.sqrt())
94 }
95
96 /// Returns the infinity norm or ∞-norm of the given (row or column) vector
97 /// or an error if the given matrix is not a vector.
98 ///
99 /// Each length of an entry is defined as the shortest distance
100 /// to the next zero instance in the ring.
101 ///
102 /// # Examples
103 /// ```
104 /// use qfall_math::{
105 /// integer::Z,
106 /// integer_mod_q::MatZq,
107 /// };
108 /// use std::str::FromStr;
109 ///
110 /// let vec = MatZq::from_str("[[1],[2],[3]] mod 3").unwrap();
111 ///
112 /// let infty_norm = vec.norm_infty().unwrap();
113 ///
114 /// // max{1, 1, 0} = 1
115 /// assert_eq!(Z::ONE, infty_norm);
116 /// ```
117 ///
118 /// # Errors and Failures
119 /// - Returns a [`MathError`] of type [`MathError::VectorFunctionCalledOnNonVector`] if
120 /// the given [`MatZq`] instance is not a (row or column) vector.
121 pub fn norm_infty(&self) -> Result<Z, MathError> {
122 if !self.is_vector() {
123 return Err(MathError::VectorFunctionCalledOnNonVector(
124 String::from("norm_infty"),
125 self.get_num_rows(),
126 self.get_num_columns(),
127 ));
128 }
129
130 let fmpz_entries = self.collect_entries();
131
132 // compute lengths of all entries in matrix with regards to modulus
133 // and find maximum length
134 let modulus = self.matrix.mod_[0];
135 let mut max = Z::ZERO;
136 for fmpz_entry in fmpz_entries {
137 let length = length(&fmpz_entry, &modulus);
138 if length > max {
139 max = length;
140 }
141 }
142
143 Ok(max)
144 }
145}
146
147#[cfg(test)]
148mod test_norm_eucl_sqrd {
149 use super::{MatZq, Z};
150 use std::str::FromStr;
151
152 /// Check whether the squared euclidean norm for row vectors
153 /// with small entries is calculated correctly
154 #[test]
155 fn row_vector_small_entries() {
156 let vec_1 = MatZq::from_str("[[1]] mod 10").unwrap();
157 let vec_2 = MatZq::from_str("[[1, 10, 100]] mod 10").unwrap();
158 let vec_3 = MatZq::from_str("[[1, 10, 100, 1000]] mod 10000").unwrap();
159
160 assert_eq!(vec_1.norm_eucl_sqrd().unwrap(), Z::ONE);
161 assert_eq!(vec_2.norm_eucl_sqrd().unwrap(), Z::ONE);
162 assert_eq!(vec_3.norm_eucl_sqrd().unwrap(), Z::from(1010101));
163 }
164
165 /// Check whether the squared euclidean norm for row vectors
166 /// with large entries is calculated correctly
167 #[test]
168 fn row_vector_large_entries() {
169 let vec = MatZq::from_str(&format!(
170 "[[{}, {}, 2]] mod {}",
171 i64::MAX,
172 i64::MIN,
173 u64::MAX
174 ))
175 .unwrap();
176 let max = Z::from(i64::MAX);
177 let cmp = Z::from(2) * &max * &max + Z::from(4);
178
179 assert_eq!(vec.norm_eucl_sqrd().unwrap(), cmp);
180 }
181
182 /// Check whether the squared euclidean norm for column vectors
183 /// with small entries is calculated correctly
184 #[test]
185 fn column_vector_small_entries() {
186 let vec_1 = MatZq::from_str("[[1],[10],[100]] mod 10").unwrap();
187 let vec_2 = MatZq::from_str("[[1],[10],[100],[1000]] mod 10000").unwrap();
188
189 assert_eq!(vec_1.norm_eucl_sqrd().unwrap(), Z::ONE);
190 assert_eq!(vec_2.norm_eucl_sqrd().unwrap(), Z::from(1010101));
191 }
192
193 /// Check whether the squared euclidean norm for column vectors
194 /// with large entries is calculated correctly
195 #[test]
196 fn column_vector_large_entries() {
197 let vec = MatZq::from_str(&format!(
198 "[[{}],[{}],[2]] mod {}",
199 i64::MAX,
200 i64::MIN,
201 u64::MAX
202 ))
203 .unwrap();
204 let max = Z::from(i64::MAX);
205 let cmp = Z::from(2) * &max * &max + Z::from(4);
206
207 assert_eq!(vec.norm_eucl_sqrd().unwrap(), cmp);
208 }
209
210 /// Check whether euclidean norm calculations of non vectors yield an error
211 #[test]
212 fn non_vector_yield_error() {
213 let mat = MatZq::from_str("[[1, 1],[10, 2]] mod 3").unwrap();
214
215 assert!(mat.norm_eucl_sqrd().is_err());
216 }
217}
218
219#[cfg(test)]
220mod test_norm_infty {
221 use super::{MatZq, Z};
222 use std::str::FromStr;
223
224 /// Check whether the infinity norm for row vectors
225 /// with small entries is calculated correctly
226 #[test]
227 fn row_vector_small_entries() {
228 let vec_1 = MatZq::from_str("[[6]] mod 10").unwrap();
229 let vec_2 = MatZq::from_str("[[1, 10, 100]] mod 1000").unwrap();
230 let vec_3 = MatZq::from_str("[[1, 10, 100, 1000]] mod 1000").unwrap();
231
232 assert_eq!(vec_1.norm_infty().unwrap(), Z::from(4));
233 assert_eq!(vec_2.norm_infty().unwrap(), Z::from(100));
234 assert_eq!(vec_3.norm_infty().unwrap(), Z::from(100));
235 }
236
237 /// Check whether the infinity norm for row vectors
238 /// with large entries is calculated correctly
239 #[test]
240 fn row_vector_large_entries() {
241 let vec = MatZq::from_str(&format!(
242 "[[{}, {}, 2]] mod {}",
243 i64::MAX,
244 i64::MIN,
245 u64::MAX
246 ))
247 .unwrap();
248 let cmp = Z::from(i64::MAX);
249
250 assert_eq!(vec.norm_infty().unwrap(), cmp);
251 }
252
253 /// Check whether the infinity norm for column vectors
254 /// with small entries is calculated correctly
255 #[test]
256 fn column_vector_small_entries() {
257 let vec_1 = MatZq::from_str("[[1],[10],[100]] mod 50").unwrap();
258 let vec_2 = MatZq::from_str("[[1],[10],[100],[1000]] mod 1999").unwrap();
259
260 assert_eq!(vec_1.norm_infty().unwrap(), Z::from(10));
261 assert_eq!(vec_2.norm_infty().unwrap(), Z::from(999));
262 }
263
264 /// Check whether the infinity norm for column vectors
265 /// with large entries is calculated correctly
266 #[test]
267 fn column_vector_large_entries() {
268 let vec = MatZq::from_str(&format!(
269 "[[{}],[{}],[2]] mod {}",
270 i64::MAX,
271 i64::MIN,
272 u64::MAX
273 ))
274 .unwrap();
275 let cmp = Z::from(i64::MAX);
276
277 assert_eq!(vec.norm_infty().unwrap(), cmp);
278 }
279
280 /// Check whether infinity norm calculations of non vectors yield an error
281 #[test]
282 fn non_vector_yield_error() {
283 let mat = MatZq::from_str("[[1, 1],[10, 2]] mod 3").unwrap();
284
285 assert!(mat.norm_infty().is_err());
286 }
287}