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
// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
use crate::integer_polynomial::IntegerPolynomial;
use alloc::vec::Vec;
use malachite_base::num::arithmetic::traits::{BalancedModPowerOf2, BalancedModPowerOf2Assign};
use malachite_base::polynomial::Polynomial;
impl BalancedModPowerOf2 for IntegerPolynomial {
type Output = Self;
/// Reduces every coefficient of an [`IntegerPolynomial`] modulo $2^k$ to the representative
/// closest to zero, taking the polynomial by value.
///
/// Each coefficient $r_i$ of the result satisfies $-2^{k-1} < r_i \leq 2^{k-1}$ and is
/// congruent to the original coefficient modulo $2^k$, which determine it uniquely, as with
/// [`BalancedModPowerOf2`] for [`Integer`](crate::integer::Integer)s; for $k = 0$ every
/// coefficient is 0. A remainder of exactly $2^{k-1}$ is positive.
///
/// Reducing can lower the degree, and can even give the zero polynomial: a leading coefficient
/// that is a multiple of $2^k$ becomes zero, and a polynomial does not hold trailing zero
/// coefficients.
///
/// # Worst-case complexity
/// $T(n, m) = O(nm)$
///
/// $M(n, m) = O(nm)$
///
/// where $T$ is time, $M$ is additional memory, $n$ is the number of coefficients, and $m$ is
/// `pow`.
///
/// # Examples
/// ```
/// use core::str::FromStr;
/// use malachite_base::num::arithmetic::traits::BalancedModPowerOf2;
/// use malachite_nz::integer_polynomial::IntegerPolynomial;
///
/// // Each coefficient goes to its balanced remainder modulo 8, and half the modulus
/// // stays positive.
/// let p = IntegerPolynomial::from_str("-19*x^2+23*x-20").unwrap();
/// assert_eq!(
/// p.clone().balanced_mod_power_of_2(3).to_string(),
/// "-3*x^2-x+4"
/// );
/// let p = IntegerPolynomial::from_str("-8*x^2+7*x-5").unwrap();
/// assert_eq!(p.clone().balanced_mod_power_of_2(3).to_string(), "-x+3");
/// ```
#[inline]
fn balanced_mod_power_of_2(mut self, pow: u64) -> Self {
self.balanced_mod_power_of_2_assign(pow);
self
}
}
impl BalancedModPowerOf2 for &IntegerPolynomial {
type Output = IntegerPolynomial;
/// Reduces every coefficient of an [`IntegerPolynomial`] modulo $2^k$ to the representative
/// closest to zero, taking the polynomial by reference.
///
/// See the documentation for the [`BalancedModPowerOf2`] implementation on
/// [`IntegerPolynomial`] that takes the polynomial by value for details.
///
/// # Worst-case complexity
/// $T(n, m) = O(nm)$
///
/// $M(n, m) = O(nm)$
///
/// where $T$ is time, $M$ is additional memory, $n$ is the number of coefficients, and $m$ is
/// `pow`.
///
/// # Examples
/// ```
/// use core::str::FromStr;
/// use malachite_base::num::arithmetic::traits::BalancedModPowerOf2;
/// use malachite_nz::integer_polynomial::IntegerPolynomial;
///
/// // Each coefficient goes to its balanced remainder modulo 8, and half the modulus
/// // stays positive.
/// let p = IntegerPolynomial::from_str("-19*x^2+23*x-20").unwrap();
/// assert_eq!((&p).balanced_mod_power_of_2(3).to_string(), "-3*x^2-x+4");
/// let p = IntegerPolynomial::from_str("-8*x^2+7*x-5").unwrap();
/// assert_eq!((&p).balanced_mod_power_of_2(3).to_string(), "-x+3");
/// ```
#[inline]
fn balanced_mod_power_of_2(self, pow: u64) -> IntegerPolynomial {
// `from_coefficients_asc` trims, which is what makes the degree fall when the leading
// coefficient reduces to zero.
IntegerPolynomial::from_coefficients_asc(
self.coefficients
.iter()
.map(|c| c.balanced_mod_power_of_2(pow))
.collect::<Vec<_>>(),
)
}
}
impl BalancedModPowerOf2Assign for IntegerPolynomial {
/// Reduces every coefficient of an [`IntegerPolynomial`] modulo $2^k$ to the representative
/// closest to zero, in place.
///
/// See the documentation for the [`BalancedModPowerOf2`] implementation on
/// [`IntegerPolynomial`] that takes the polynomial by value for details.
///
/// # Worst-case complexity
/// $T(n, m) = O(nm)$
///
/// $M(n, m) = O(m)$
///
/// where $T$ is time, $M$ is additional memory, $n$ is the number of coefficients, and $m$ is
/// `pow`.
///
/// # Examples
/// ```
/// use core::str::FromStr;
/// use malachite_base::num::arithmetic::traits::BalancedModPowerOf2Assign;
/// use malachite_nz::integer_polynomial::IntegerPolynomial;
///
/// let mut p = IntegerPolynomial::from_str("-19*x^2+23*x-20").unwrap();
/// p.balanced_mod_power_of_2_assign(3);
/// assert_eq!(p.to_string(), "-3*x^2-x+4");
/// ```
fn balanced_mod_power_of_2_assign(&mut self, pow: u64) {
for c in &mut self.coefficients {
c.balanced_mod_power_of_2_assign(pow);
}
self.trim();
}
}