malachite_base/unsigned_polynomial/arithmetic/
mod_neg.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::num::arithmetic::traits::{ModIsReduced, ModNeg, ModNegAssign};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_polynomial::UnsignedPolynomial;
12
13fn assert_reduced<T: PrimitiveUnsigned>(p: &UnsignedPolynomial<T>, m: T) {
14    assert!(
15        p.mod_is_reduced(&m),
16        "self must be reduced mod m, but {p} has a coefficient >= {m}"
17    );
18}
19
20// Negates every coefficient modulo m. The coefficients are reduced, so a nonzero one stays nonzero
21// and nothing needs trimming.
22fn negate<T: PrimitiveUnsigned>(coefficients: &mut [T], m: T) {
23    for c in coefficients {
24        if *c != T::ZERO {
25            *c = m - *c;
26        }
27    }
28}
29
30impl<T: PrimitiveUnsigned> ModNeg<T> for UnsignedPolynomial<T> {
31    type Output = Self;
32
33    /// Negates an [`UnsignedPolynomial`] modulo `m`, taking the polynomial by value. The
34    /// coefficients must already be reduced modulo `m`.
35    ///
36    /// Each nonzero coefficient $c$ becomes $m - c$, which is also nonzero, so the degree is
37    /// unchanged. The zero polynomial is its own negation.
38    ///
39    /// $$
40    /// f(p, m) = -p \bmod m.
41    /// $$
42    ///
43    /// # Worst-case complexity
44    /// $T(n) = O(n)$
45    ///
46    /// $M(n) = O(1)$
47    ///
48    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
49    ///
50    /// # Panics
51    /// Panics if `m` is 0, or if any coefficient of `self` is greater than or equal to `m`.
52    ///
53    /// # Examples
54    /// ```
55    /// use core::str::FromStr;
56    /// use malachite_base::num::arithmetic::traits::ModNeg;
57    /// use malachite_base::num::basic::traits::Zero;
58    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
59    ///
60    /// let p = UnsignedPolynomial::<u8>::from_str("5*x^2+x+3").unwrap();
61    /// assert_eq!(p.clone().mod_neg(7).to_string(), "2*x^2+6*x+4");
62    /// assert_eq!(
63    ///     UnsignedPolynomial::<u8>::ZERO.mod_neg(7),
64    ///     UnsignedPolynomial::<u8>::ZERO
65    /// );
66    /// ```
67    ///
68    /// This is equivalent to `nmod_poly_neg` from `nmod_poly/neg.c`, FLINT 3.6.0.
69    #[inline]
70    fn mod_neg(mut self, m: T) -> Self {
71        self.mod_neg_assign(m);
72        self
73    }
74}
75
76impl<T: PrimitiveUnsigned> ModNeg<T> for &UnsignedPolynomial<T> {
77    type Output = UnsignedPolynomial<T>;
78
79    /// Negates an [`UnsignedPolynomial`] modulo `m`, taking the polynomial by reference. The
80    /// coefficients must already be reduced modulo `m`.
81    ///
82    /// Each nonzero coefficient $c$ becomes $m - c$, which is also nonzero, so the degree is
83    /// unchanged. The zero polynomial is its own negation.
84    ///
85    /// $$
86    /// f(p, m) = -p \bmod m.
87    /// $$
88    ///
89    /// # Worst-case complexity
90    /// $T(n) = O(n)$
91    ///
92    /// $M(n) = O(n)$
93    ///
94    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
95    ///
96    /// # Panics
97    /// Panics if `m` is 0, or if any coefficient of `self` is greater than or equal to `m`.
98    ///
99    /// # Examples
100    /// ```
101    /// use core::str::FromStr;
102    /// use malachite_base::num::arithmetic::traits::ModNeg;
103    /// use malachite_base::num::basic::traits::Zero;
104    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
105    ///
106    /// let p = UnsignedPolynomial::<u8>::from_str("5*x^2+x+3").unwrap();
107    /// assert_eq!((&p).mod_neg(7).to_string(), "2*x^2+6*x+4");
108    /// assert_eq!(
109    ///     (&UnsignedPolynomial::<u8>::ZERO).mod_neg(7),
110    ///     UnsignedPolynomial::<u8>::ZERO
111    /// );
112    /// ```
113    ///
114    /// This is equivalent to `nmod_poly_neg` from `nmod_poly/neg.c`, FLINT 3.6.0.
115    fn mod_neg(self, m: T) -> UnsignedPolynomial<T> {
116        assert_reduced(self, m);
117        let mut coefficients = self.coefficients.clone();
118        negate(&mut coefficients, m);
119        UnsignedPolynomial { coefficients }
120    }
121}
122
123impl<T: PrimitiveUnsigned> ModNegAssign<T> for UnsignedPolynomial<T> {
124    /// Negates an [`UnsignedPolynomial`] modulo `m`, in place. The coefficients must already be
125    /// reduced modulo `m`.
126    ///
127    /// See [`mod_neg`](ModNeg::mod_neg).
128    ///
129    /// # Worst-case complexity
130    /// $T(n) = O(n)$
131    ///
132    /// $M(n) = O(1)$
133    ///
134    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
135    ///
136    /// # Panics
137    /// Panics if `m` is 0, or if any coefficient of `self` is greater than or equal to `m`.
138    ///
139    /// # Examples
140    /// ```
141    /// use core::str::FromStr;
142    /// use malachite_base::num::arithmetic::traits::ModNegAssign;
143    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
144    ///
145    /// let mut p = UnsignedPolynomial::<u8>::from_str("5*x^2+x+3").unwrap();
146    /// p.mod_neg_assign(7);
147    /// assert_eq!(p.to_string(), "2*x^2+6*x+4");
148    /// ```
149    fn mod_neg_assign(&mut self, m: T) {
150        assert_reduced(self, m);
151        negate(&mut self.coefficients, m);
152    }
153}
malachite_base/unsigned_polynomial/arithmetic/mod_neg.rs

malachite_base/unsigned_polynomial/arithmetic/
mod_neg.rs
