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