malachite_base/num/arithmetic/mod_shl.rs
1// Copyright © 2025 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::{ModShl, ModShlAssign, UnsignedAbs};
10use crate::num::basic::integers::PrimitiveInt;
11use crate::num::basic::signeds::PrimitiveSigned;
12use crate::num::basic::unsigneds::PrimitiveUnsigned;
13use crate::num::conversion::traits::ExactFrom;
14use core::ops::{Shr, ShrAssign};
15
16fn mod_shl_unsigned<T: PrimitiveUnsigned, U: PrimitiveUnsigned>(x: T, other: U, m: T) -> T
17where
18 u64: ExactFrom<U>,
19{
20 assert!(x < m, "x must be reduced mod m, but {x} >= {m}");
21 if other == U::ZERO {
22 x
23 } else if m == T::ONE || m == T::TWO {
24 T::ZERO
25 } else {
26 x.mod_mul(T::TWO.mod_pow(u64::exact_from(other), m), m)
27 }
28}
29
30fn mod_shl_assign_unsigned<T: PrimitiveUnsigned, U: PrimitiveUnsigned>(x: &mut T, other: U, m: T)
31where
32 u64: ExactFrom<U>,
33{
34 assert!(*x < m, "x must be reduced mod m, but {x} >= {m}");
35 if other == U::ZERO {
36 } else if m == T::ONE || m == T::TWO {
37 *x = T::ZERO;
38 } else {
39 x.mod_mul_assign(T::TWO.mod_pow(u64::exact_from(other), m), m);
40 }
41}
42
43macro_rules! impl_mod_shl_unsigned {
44 ($t:ident) => {
45 macro_rules! impl_mod_shl_unsigned_inner {
46 ($u:ident) => {
47 impl ModShl<$u, $t> for $t {
48 type Output = $t;
49
50 /// Left-shifts a number (multiplies it by a power of 2) modulo a number $m$.
51 /// The number must be already reduced modulo $m$.
52 ///
53 /// $f(x, n, m) = y$, where $x, y < m$ and $2^nx \equiv y \mod m$.
54 ///
55 /// # Worst-case complexity
56 /// $T(n) = O(n)$
57 ///
58 /// $M(n) = O(1)$
59 ///
60 /// where $T$ is time, $M$ is additional memory, and $n$ is
61 /// `other.significant_bits()`.
62 ///
63 /// # Panics
64 /// Panics if `self` is greater than or equal to `m`.
65 ///
66 /// # Examples
67 /// See [here](super::mod_shl#mod_shl).
68 #[inline]
69 fn mod_shl(self, other: $u, m: $t) -> $t {
70 mod_shl_unsigned(self, other, m)
71 }
72 }
73
74 impl ModShlAssign<$u, $t> for $t {
75 /// Left-shifts a number (multiplies it by a power of 2) modulo a number $m$, in
76 /// place. The number must be already reduced modulo $m$.
77 ///
78 /// $x \gets y$, where $x, y < m$ and $2^nx \equiv y \mod m$.
79 ///
80 /// # Worst-case complexity
81 /// $T(n) = O(n)$
82 ///
83 /// $M(n) = O(1)$
84 ///
85 /// where $T$ is time, $M$ is additional memory, and $n$ is
86 /// `other.significant_bits()`.
87 ///
88 /// # Panics
89 /// Panics if `self` is greater than or equal to `m`.
90 ///
91 /// # Examples
92 /// See [here](super::mod_shl#mod_shl_assign).
93 #[inline]
94 fn mod_shl_assign(&mut self, other: $u, m: $t) {
95 mod_shl_assign_unsigned(self, other, m);
96 }
97 }
98 };
99 }
100 apply_to_unsigneds!(impl_mod_shl_unsigned_inner);
101 };
102}
103apply_to_unsigneds!(impl_mod_shl_unsigned);
104
105fn mod_shl_signed<
106 T: ModShl<U, T, Output = T> + PrimitiveInt + Shr<U, Output = T>,
107 U: PrimitiveUnsigned,
108 S: PrimitiveSigned + UnsignedAbs<Output = U>,
109>(
110 x: T,
111 other: S,
112 m: T,
113) -> T {
114 assert!(x < m, "x must be reduced mod m, but {x} >= {m}");
115 let other_abs = other.unsigned_abs();
116 if other >= S::ZERO {
117 x.mod_shl(other_abs, m)
118 } else {
119 let width = U::wrapping_from(T::WIDTH);
120 if width != U::ZERO && other_abs >= width {
121 T::ZERO
122 } else {
123 x >> other_abs
124 }
125 }
126}
127
128fn mod_shl_assign_signed<
129 T: ModShlAssign<U, T> + PrimitiveUnsigned + ShrAssign<U>,
130 U: PrimitiveUnsigned,
131 S: PrimitiveSigned + UnsignedAbs<Output = U>,
132>(
133 x: &mut T,
134 other: S,
135 m: T,
136) {
137 assert!(*x < m, "x must be reduced mod m, but {x} >= {m}");
138 let other_abs = other.unsigned_abs();
139 if other >= S::ZERO {
140 x.mod_shl_assign(other_abs, m);
141 } else {
142 let width = U::wrapping_from(T::WIDTH);
143 if width != U::ZERO && other_abs >= width {
144 *x = T::ZERO;
145 } else {
146 *x >>= other_abs;
147 }
148 }
149}
150
151macro_rules! impl_mod_shl_signed {
152 ($t:ident) => {
153 macro_rules! impl_mod_shl_signed_inner {
154 ($u:ident) => {
155 impl ModShl<$u, $t> for $t {
156 type Output = $t;
157
158 /// Left-shifts a number (multiplies it by a power of 2) modulo a number $m$.
159 /// The number must be already reduced modulo $m$.
160 ///
161 /// $f(x, n, m) = y$, where $x, y < m$ and $\lfloor 2^nx \rfloor \equiv y \mod
162 /// m$.
163 ///
164 /// # Worst-case complexity
165 /// $T(n) = O(n)$
166 ///
167 /// $M(n) = O(1)$
168 ///
169 /// where $T$ is time, $M$ is additional memory, and $n$ is
170 /// `other.significant_bits()`.
171 ///
172 /// # Panics
173 /// Panics if `self` is greater than or equal to `m`.
174 ///
175 /// # Examples
176 /// See [here](super::mod_shl#mod_shl).
177 #[inline]
178 fn mod_shl(self, other: $u, m: $t) -> $t {
179 mod_shl_signed(self, other, m)
180 }
181 }
182
183 impl ModShlAssign<$u, $t> for $t {
184 /// Left-shifts a number (multiplies it by a power of 2) modulo a number $m$, in
185 /// place. The number must be already reduced modulo $m$.
186 ///
187 /// $x \gets y$, where $x, y < m$ and $\lfloor 2^nx \rfloor \equiv y \mod m$.
188 ///
189 /// # Worst-case complexity
190 /// $T(n) = O(n)$
191 ///
192 /// $M(n) = O(1)$
193 ///
194 /// where $T$ is time, $M$ is additional memory, and $n$ is
195 /// `other.significant_bits()`.
196 ///
197 /// # Panics
198 /// Panics if `self` is greater than or equal to `m`.
199 ///
200 /// # Examples
201 /// See [here](super::mod_shl#mod_shl_assign).
202 #[inline]
203 fn mod_shl_assign(&mut self, other: $u, m: $t) {
204 mod_shl_assign_signed(self, other, m);
205 }
206 }
207 };
208 }
209 apply_to_signeds!(impl_mod_shl_signed_inner);
210 };
211}
212apply_to_unsigneds!(impl_mod_shl_signed);