malachite_nz/integer_polynomial/arithmetic/
l2_norm_squared.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::integer_polynomial::IntegerPolynomial;
10use crate::natural::Natural;
11use malachite_base::num::arithmetic::traits::AddMulAssign;
12use malachite_base::num::basic::traits::Zero;
13use malachite_base::polynomial::L2NormSquared;
14
15impl L2NormSquared for &IntegerPolynomial {
16    type Output = Natural;
17
18    /// Computes the sum of the squares of an [`IntegerPolynomial`]'s coefficients, which is the
19    /// square of its $L^2$ norm.
20    ///
21    /// $$
22    /// f(p) = \sum_i p_i^2.
23    /// $$
24    ///
25    /// # Worst-case complexity
26    /// $T(n) = O(n \log n \log\log n)$
27    ///
28    /// $M(n) = O(n)$
29    ///
30    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
31    /// coefficients.
32    ///
33    /// # Examples
34    /// ```
35    /// use core::str::FromStr;
36    /// use malachite_base::polynomial::L2NormSquared;
37    /// use malachite_nz::integer_polynomial::IntegerPolynomial;
38    ///
39    /// assert_eq!(
40    ///     IntegerPolynomial::from_str("x^2-3*x+2")
41    ///         .unwrap()
42    ///         .l2_norm_squared(),
43    ///     14u32
44    /// );
45    /// assert_eq!(
46    ///     IntegerPolynomial::from_str("0").unwrap().l2_norm_squared(),
47    ///     0u32
48    /// );
49    /// assert_eq!(
50    ///     IntegerPolynomial::from_str("-5").unwrap().l2_norm_squared(),
51    ///     25u32
52    /// );
53    /// ```
54    ///
55    /// This is the dot product of the coefficients with themselves that `_fmpz_poly_2norm` in
56    /// `fmpz_poly/2norm.c`, FLINT 3.6.0, computes before taking the square root.
57    fn l2_norm_squared(self) -> Natural {
58        let mut sum = Natural::ZERO;
59        for c in &self.coefficients {
60            let a = c.unsigned_abs_ref();
61            sum.add_mul_assign(a, a);
62        }
63        sum
64    }
65}
malachite_nz/integer_polynomial/arithmetic/l2_norm_squared.rs

malachite_nz/integer_polynomial/arithmetic/
l2_norm_squared.rs
