qfall_math/integer/poly_over_z/
norm.rs

1// Copyright © 2023 Phil Milewski
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 polynomials.
11
12use crate::{
13    integer::{PolyOverZ, Z},
14    traits::{GetCoefficient, Pow},
15};
16use std::cmp::max;
17
18impl PolyOverZ {
19    /// Returns the squared Euclidean norm or squared 2-norm of the given polynomial.
20    /// The squared Euclidean norm for a polynomial is obtained by treating the coefficients
21    /// of the polynomial as a vector and then applying the standard squared Euclidean norm.
22    ///
23    /// # Examples
24    /// ```
25    /// use qfall_math::integer::{PolyOverZ, Z};
26    /// use std::str::FromStr;
27    ///
28    /// let poly = PolyOverZ::from_str("3  1 2 3").unwrap();
29    ///
30    /// let sqrd_2_norm = poly.norm_eucl_sqrd();
31    ///
32    /// // 1*1 + 2*2 + 3*3 = 14
33    /// assert_eq!(Z::from(14), sqrd_2_norm);
34    /// ```
35    pub fn norm_eucl_sqrd(&self) -> Z {
36        let mut res = Z::ZERO;
37
38        for i in 0..=self.get_degree() {
39            let coeff = unsafe { self.get_coeff_unchecked(i) };
40            res += coeff.pow(2).unwrap();
41        }
42        res
43    }
44
45    /// Returns the infinity norm or the maximal absolute value of a
46    /// coefficient of the given polynomial.
47    /// The infinity norm for a polynomial is obtained by treating the coefficients
48    /// of the polynomial as a vector and then applying the standard infinity norm.
49    ///
50    /// # Examples
51    /// ```
52    /// use qfall_math::integer::{PolyOverZ, Z};
53    /// use std::str::FromStr;
54    ///
55    /// let poly = PolyOverZ::from_str("3  1 2 3").unwrap();
56    ///
57    /// let infty_norm = poly.norm_infty();
58    ///
59    /// // max coefficient is 3
60    /// assert_eq!(Z::from(3), infty_norm);
61    /// ```
62    pub fn norm_infty(&self) -> Z {
63        let mut res = Z::ZERO;
64        for i in 0..=self.get_degree() {
65            if res < unsafe { self.get_coeff_unchecked(i).abs() } {
66                res = max(res, unsafe { self.get_coeff_unchecked(i).abs() });
67            }
68        }
69        res
70    }
71}
72
73#[cfg(test)]
74mod test_norm_eucl_sqrd {
75    use super::{PolyOverZ, Z};
76    use std::str::FromStr;
77
78    /// Check whether the squared euclidean norm for polynomials
79    /// with small coefficients is calculated correctly
80    #[test]
81    fn poly_small_coefficient() {
82        let poly_1 = PolyOverZ::default();
83        let poly_2 = PolyOverZ::from_str("3  1 2 3").unwrap();
84        let poly_3 = PolyOverZ::from_str("3  1 20 90").unwrap();
85
86        assert_eq!(poly_1.norm_eucl_sqrd(), Z::ZERO);
87        assert_eq!(poly_2.norm_eucl_sqrd(), Z::from(14));
88        assert_eq!(poly_3.norm_eucl_sqrd(), Z::from(8501));
89    }
90
91    /// Check whether the squared euclidean norm for polynomials
92    /// with small coefficients is calculated correctly
93    #[test]
94    fn poly_large_coefficient() {
95        let poly_1 = PolyOverZ::from(u64::MAX);
96        let poly_2 =
97            PolyOverZ::from_str(&format!("3  {} {} {}", u64::MAX, i64::MIN, i64::MAX)).unwrap();
98
99        assert_eq!(
100            poly_1.norm_eucl_sqrd(),
101            Z::from(u64::MAX) * Z::from(u64::MAX)
102        );
103        assert_eq!(
104            poly_2.norm_eucl_sqrd(),
105            Z::from(u64::MAX) * Z::from(u64::MAX)
106                + Z::from(i64::MAX) * Z::from(i64::MAX)
107                + Z::from(i64::MIN) * Z::from(i64::MIN)
108        );
109    }
110}
111
112#[cfg(test)]
113mod test_norm_infty {
114    use super::{PolyOverZ, Z};
115    use std::str::FromStr;
116
117    /// Check whether the infinity norm for polynomials
118    /// with small coefficients is calculated correctly
119    #[test]
120    fn poly_small_coefficient() {
121        let poly_1 = PolyOverZ::default();
122        let poly_2 = PolyOverZ::from_str("3  1 2 3").unwrap();
123        let poly_3 = PolyOverZ::from_str("3  1 2010 90").unwrap();
124
125        assert_eq!(poly_1.norm_infty(), Z::ZERO);
126        assert_eq!(poly_2.norm_infty(), Z::from(3));
127        assert_eq!(poly_3.norm_infty(), Z::from(2010));
128    }
129
130    /// Check whether the infinity norm for polynomials
131    /// with small coefficients is calculated correctly
132    #[test]
133    fn poly_large_coefficient() {
134        let poly_1 = PolyOverZ::from(u64::MAX);
135        let poly_2 =
136            PolyOverZ::from_str(&format!("3  {} {} {}", u64::MAX, i64::MIN, i64::MAX)).unwrap();
137
138        assert_eq!(poly_1.norm_infty(), Z::from(u64::MAX));
139        assert_eq!(poly_2.norm_infty(), Z::from(u64::MAX));
140    }
141}
qfall_math/integer/poly_over_z/norm.rs

qfall_math/integer/poly_over_z/
norm.rs
