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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
// 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},
rational::Q,
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 Euclidean norm or 2-norm of the given polynomial.
/// The Euclidean norm for a polynomial is obtained by treating the coefficients
/// of the polynomial as a vector and then applying the standard Euclidean norm.
///
/// # Examples
/// ```
/// use qfall_math::{integer::PolyOverZ, rational::Q};
/// use std::str::FromStr;
///
/// let poly = PolyOverZ::from_str("1 3").unwrap();
///
/// let norm = poly.norm_eucl();
///
/// // sqrt(3^2) = 3
/// assert_eq!(Q::from(3), norm);
/// ```
pub fn norm_eucl(&self) -> Q {
self.norm_eucl_sqrd().sqrt()
}
/// 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
}
/// Outputs the hamming weight of `self`, i.e. it returns the number of
/// non-zero coefficients in the polynomial.
///
/// # Examples
/// ```
/// use qfall_math::integer::PolyOverZ;
/// use std::str::FromStr;
///
/// let poly = PolyOverZ::from_str("5 1 2 3 0 4").unwrap();
///
/// let hamming_weight = poly.hamming_weight();
///
/// assert_eq!(4, hamming_weight);
/// ```
pub fn hamming_weight(&self) -> i64 {
let mut hamming_weight = 0;
for i in 0..=self.get_degree() {
let coeff = unsafe { self.get_coeff_unchecked(i) };
if !coeff.is_zero() {
hamming_weight += 1;
}
}
hamming_weight
}
}
#[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));
}
}
#[cfg(test)]
mod test_hamming_weight {
use super::PolyOverZ;
use std::str::FromStr;
/// Ensures that the hamming weight is computed correctly.
#[test]
fn hamming_weight() {
let poly0 = PolyOverZ::default();
let poly1 = PolyOverZ::from_str("6 0 0 2 3 4 5").unwrap();
let hw0 = poly0.hamming_weight();
let hw1 = poly1.hamming_weight();
assert_eq!(0, hw0);
assert_eq!(4, hw1);
}
}