malachite_base/unsigned_polynomial/arithmetic/mod_power_of_2_shl.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::{ModPowerOf2IsReduced, ModPowerOf2Shl, ModPowerOf2ShlAssign};
10use crate::num::basic::traits::Zero;
11use crate::num::basic::unsigneds::PrimitiveUnsigned;
12use crate::unsigned_polynomial::UnsignedPolynomial;
13
14fn assert_reduced<T: PrimitiveUnsigned>(p: &UnsignedPolynomial<T>, pow: u64) {
15 assert!(pow <= T::WIDTH);
16 assert!(
17 p.mod_power_of_2_is_reduced(pow),
18 "self must be reduced mod 2^pow, but {p} has a coefficient >= 2^{pow}"
19 );
20}
21
22// The shift amount as a `u64`, or `None` if it is at least `pow`, in which case every coefficient
23// becomes zero. `pow` is at most `T::WIDTH`, which is at most 128, so it fits in every unsigned
24// type.
25fn shift_below_pow<U: PrimitiveUnsigned>(bits: U, pow: u64) -> Option<u64> {
26 if bits >= U::exact_from(pow) {
27 None
28 } else {
29 Some(bits.exact_into())
30 }
31}
32
33// Shifts every coefficient left by `bits` modulo 2^pow: only the low `pow - bits` bits of each
34// survive, so the shift cannot overflow, a coefficient can become zero, and the result is trimmed.
35fn mod_power_of_2_shl_ref<T: PrimitiveUnsigned, U: PrimitiveUnsigned>(
36 p: &UnsignedPolynomial<T>,
37 bits: U,
38 pow: u64,
39) -> UnsignedPolynomial<T> {
40 assert_reduced(p, pow);
41 let Some(bits) = shift_below_pow(bits, pow) else {
42 return UnsignedPolynomial::ZERO;
43 };
44 let mut q = UnsignedPolynomial {
45 coefficients: p
46 .coefficients
47 .iter()
48 .map(|&c| c.mod_power_of_2(pow - bits) << bits)
49 .collect(),
50 };
51 q.trim();
52 q
53}
54
55fn mod_power_of_2_shl_assign<T: PrimitiveUnsigned, U: PrimitiveUnsigned>(
56 p: &mut UnsignedPolynomial<T>,
57 bits: U,
58 pow: u64,
59) {
60 assert_reduced(p, pow);
61 let Some(bits) = shift_below_pow(bits, pow) else {
62 p.coefficients.clear();
63 return;
64 };
65 if bits != 0 {
66 for c in &mut p.coefficients {
67 *c = c.mod_power_of_2(pow - bits) << bits;
68 }
69 p.trim();
70 }
71}
72
73macro_rules! impl_mod_power_of_2_shl_unsigned {
74 ($t:ident) => {
75 impl<T: PrimitiveUnsigned> ModPowerOf2Shl<$t> for UnsignedPolynomial<T> {
76 type Output = UnsignedPolynomial<T>;
77
78 /// Left-shifts an [`UnsignedPolynomial`] (multiplies it by a power of 2) modulo $2^k$,
79 /// taking the polynomial by value. The coefficients must already be reduced modulo
80 /// $2^k$.
81 ///
82 /// Every coefficient is shifted and reduced. Coefficients can become zero, so the
83 /// degree can drop; if `bits` is at least `pow`, the result is zero.
84 ///
85 /// $$
86 /// f(p, m, k) = 2^mp \bmod 2^k.
87 /// $$
88 ///
89 /// # Worst-case complexity
90 /// $T(n) = O(n)$
91 ///
92 /// $M(n) = O(1)$
93 ///
94 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
95 ///
96 /// # Panics
97 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` is
98 /// greater than or equal to $2^k$.
99 ///
100 /// # Examples
101 /// See [here](super::mod_power_of_2_shl#mod_power_of_2_shl).
102 #[inline]
103 fn mod_power_of_2_shl(mut self, bits: $t, pow: u64) -> UnsignedPolynomial<T> {
104 mod_power_of_2_shl_assign(&mut self, bits, pow);
105 self
106 }
107 }
108
109 impl<T: PrimitiveUnsigned> ModPowerOf2Shl<$t> for &UnsignedPolynomial<T> {
110 type Output = UnsignedPolynomial<T>;
111
112 /// Left-shifts an [`UnsignedPolynomial`] (multiplies it by a power of 2) modulo $2^k$,
113 /// taking the polynomial by reference. The coefficients must already be reduced modulo
114 /// $2^k$.
115 ///
116 /// Every coefficient is shifted and reduced. Coefficients can become zero, so the
117 /// degree can drop; if `bits` is at least `pow`, the result is zero.
118 ///
119 /// $$
120 /// f(p, m, k) = 2^mp \bmod 2^k.
121 /// $$
122 ///
123 /// # Worst-case complexity
124 /// $T(n) = O(n)$
125 ///
126 /// $M(n) = O(n)$
127 ///
128 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
129 ///
130 /// # Panics
131 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` is
132 /// greater than or equal to $2^k$.
133 ///
134 /// # Examples
135 /// See [here](super::mod_power_of_2_shl#mod_power_of_2_shl).
136 #[inline]
137 fn mod_power_of_2_shl(self, bits: $t, pow: u64) -> UnsignedPolynomial<T> {
138 mod_power_of_2_shl_ref(self, bits, pow)
139 }
140 }
141
142 impl<T: PrimitiveUnsigned> ModPowerOf2ShlAssign<$t> for UnsignedPolynomial<T> {
143 /// Left-shifts an [`UnsignedPolynomial`] (multiplies it by a power of 2) modulo $2^k$,
144 /// in place. The coefficients must already be reduced modulo $2^k$.
145 ///
146 /// Every coefficient is shifted and reduced. Coefficients can become zero, so the
147 /// degree can drop; if `bits` is at least `pow`, the result is zero.
148 ///
149 /// $$
150 /// p \gets 2^mp \bmod 2^k.
151 /// $$
152 ///
153 /// # Worst-case complexity
154 /// $T(n) = O(n)$
155 ///
156 /// $M(n) = O(1)$
157 ///
158 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
159 ///
160 /// # Panics
161 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` is
162 /// greater than or equal to $2^k$.
163 ///
164 /// # Examples
165 /// See [here](super::mod_power_of_2_shl#mod_power_of_2_shl_assign).
166 #[inline]
167 fn mod_power_of_2_shl_assign(&mut self, bits: $t, pow: u64) {
168 mod_power_of_2_shl_assign(self, bits, pow);
169 }
170 }
171 };
172}
173apply_to_unsigneds!(impl_mod_power_of_2_shl_unsigned);