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