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

qfall_math/rational/poly_over_q/
norm.rs
