malachite_nz/integer/arithmetic/add_mul_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::integer::Integer;
10use malachite_base::num::arithmetic::traits::{AddMul, AddMulAssign, AddMulShl, AddMulShlAssign};
11
12impl AddMulShl<Self, Self> for Integer {
13 type Output = Self;
14
15 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`,
16 /// taking all three by value.
17 ///
18 /// $f(x, y, z, k) = x + yz2^k$.
19 ///
20 /// When `bits` is 0, this is [`AddMul`].
21 ///
22 /// # Worst-case complexity
23 /// $T(n, m) = O(m + n \log n \log\log n)$
24 ///
25 /// $M(n, m) = O(m + n \log n)$
26 ///
27 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
28 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
29 ///
30 /// # Examples
31 /// ```
32 /// use malachite_base::num::arithmetic::traits::{AddMulShl, Pow};
33 /// use malachite_nz::integer::Integer;
34 ///
35 /// assert_eq!(
36 /// Integer::from(10).add_mul_shl(Integer::from(3), Integer::from(4), 2),
37 /// 58
38 /// );
39 /// assert_eq!(
40 /// Integer::from(-10).add_mul_shl(Integer::from(3), Integer::from(-4), 2),
41 /// -58
42 /// );
43 /// assert_eq!(
44 /// Integer::from(10u32).pow(12).add_mul_shl(
45 /// Integer::from(0x10000),
46 /// -Integer::from(10u32).pow(12),
47 /// 3
48 /// ),
49 /// -524287000000000000i64
50 /// );
51 /// ```
52 #[inline]
53 fn add_mul_shl(mut self, y: Self, z: Self, bits: u64) -> Self {
54 self.add_mul_shl_assign(y, z, bits);
55 self
56 }
57}
58
59impl<'b> AddMulShl<Self, &'b Self> for Integer {
60 type Output = Self;
61
62 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`,
63 /// taking the first [`Integer`] by value, the second by value, and the third by reference.
64 ///
65 /// $f(x, y, z, k) = x + yz2^k$.
66 ///
67 /// # Worst-case complexity
68 /// $T(n, m) = O(m + n \log n \log\log n)$
69 ///
70 /// $M(n, m) = O(m + n \log n)$
71 ///
72 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
73 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
74 ///
75 /// # Examples
76 /// ```
77 /// use malachite_base::num::arithmetic::traits::{AddMulShl, Pow};
78 /// use malachite_nz::integer::Integer;
79 ///
80 /// assert_eq!(
81 /// Integer::from(10).add_mul_shl(Integer::from(3), &Integer::from(4), 2),
82 /// 58
83 /// );
84 /// assert_eq!(
85 /// Integer::from(-10).add_mul_shl(Integer::from(3), &Integer::from(-4), 2),
86 /// -58
87 /// );
88 /// assert_eq!(
89 /// Integer::from(10u32).pow(12).add_mul_shl(
90 /// Integer::from(0x10000),
91 /// &-Integer::from(10u32).pow(12),
92 /// 3
93 /// ),
94 /// -524287000000000000i64
95 /// );
96 /// ```
97 #[inline]
98 fn add_mul_shl(mut self, y: Self, z: &'b Self, bits: u64) -> Self {
99 self.add_mul_shl_assign(y, z, bits);
100 self
101 }
102}
103
104impl<'a> AddMulShl<&'a Self, Self> for Integer {
105 type Output = Self;
106
107 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`,
108 /// taking the first [`Integer`] by value, the second by reference, and the third by value.
109 ///
110 /// $f(x, y, z, k) = x + yz2^k$.
111 ///
112 /// # Worst-case complexity
113 /// $T(n, m) = O(m + n \log n \log\log n)$
114 ///
115 /// $M(n, m) = O(m + n \log n)$
116 ///
117 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
118 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
119 ///
120 /// # Examples
121 /// ```
122 /// use malachite_base::num::arithmetic::traits::{AddMulShl, Pow};
123 /// use malachite_nz::integer::Integer;
124 ///
125 /// assert_eq!(
126 /// Integer::from(10).add_mul_shl(&Integer::from(3), Integer::from(4), 2),
127 /// 58
128 /// );
129 /// assert_eq!(
130 /// Integer::from(-10).add_mul_shl(&Integer::from(3), Integer::from(-4), 2),
131 /// -58
132 /// );
133 /// assert_eq!(
134 /// Integer::from(10u32).pow(12).add_mul_shl(
135 /// &Integer::from(0x10000),
136 /// -Integer::from(10u32).pow(12),
137 /// 3
138 /// ),
139 /// -524287000000000000i64
140 /// );
141 /// ```
142 #[inline]
143 fn add_mul_shl(mut self, y: &'a Self, z: Self, bits: u64) -> Self {
144 self.add_mul_shl_assign(y, z, bits);
145 self
146 }
147}
148
149impl<'a, 'b> AddMulShl<&'a Self, &'b Self> for Integer {
150 type Output = Self;
151
152 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`,
153 /// taking the first [`Integer`] by value, the second by reference, and the third by reference.
154 ///
155 /// $f(x, y, z, k) = x + yz2^k$.
156 ///
157 /// # Worst-case complexity
158 /// $T(n, m) = O(m + n \log n \log\log n)$
159 ///
160 /// $M(n, m) = O(m + n \log n)$
161 ///
162 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
163 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
164 ///
165 /// # Examples
166 /// ```
167 /// use malachite_base::num::arithmetic::traits::{AddMulShl, Pow};
168 /// use malachite_nz::integer::Integer;
169 ///
170 /// assert_eq!(
171 /// Integer::from(10).add_mul_shl(&Integer::from(3), &Integer::from(4), 2),
172 /// 58
173 /// );
174 /// assert_eq!(
175 /// Integer::from(-10).add_mul_shl(&Integer::from(3), &Integer::from(-4), 2),
176 /// -58
177 /// );
178 /// assert_eq!(
179 /// Integer::from(10u32).pow(12).add_mul_shl(
180 /// &Integer::from(0x10000),
181 /// &-Integer::from(10u32).pow(12),
182 /// 3
183 /// ),
184 /// -524287000000000000i64
185 /// );
186 /// ```
187 #[inline]
188 fn add_mul_shl(mut self, y: &'a Self, z: &'b Self, bits: u64) -> Self {
189 self.add_mul_shl_assign(y, z, bits);
190 self
191 }
192}
193
194impl AddMulShl<&Integer, &Integer> for &Integer {
195 type Output = Integer;
196
197 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`,
198 /// taking all three by reference.
199 ///
200 /// $f(x, y, z, k) = x + yz2^k$.
201 ///
202 /// # Worst-case complexity
203 /// $T(n, m) = O(m + n \log n \log\log n)$
204 ///
205 /// $M(n, m) = O(m + n \log n)$
206 ///
207 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
208 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
209 ///
210 /// # Examples
211 /// ```
212 /// use malachite_base::num::arithmetic::traits::{AddMulShl, Pow};
213 /// use malachite_nz::integer::Integer;
214 ///
215 /// assert_eq!(
216 /// (&Integer::from(10)).add_mul_shl(&Integer::from(3), &Integer::from(4), 2),
217 /// 58
218 /// );
219 /// assert_eq!(
220 /// (&Integer::from(-10)).add_mul_shl(&Integer::from(3), &Integer::from(-4), 2),
221 /// -58
222 /// );
223 /// assert_eq!(
224 /// (&Integer::from(10u32).pow(12)).add_mul_shl(
225 /// &Integer::from(0x10000),
226 /// &-Integer::from(10u32).pow(12),
227 /// 3
228 /// ),
229 /// -524287000000000000i64
230 /// );
231 /// ```
232 fn add_mul_shl(self, y: &Integer, z: &Integer, bits: u64) -> Integer {
233 if bits == 0 {
234 self.add_mul(y, z)
235 } else {
236 self + ((y * z) << bits)
237 }
238 }
239}
240
241impl AddMulShlAssign<Self, Self> for Integer {
242 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`, in
243 /// place, taking both [`Integer`]s on the right-hand side by value.
244 ///
245 /// $x \gets x + yz2^k$.
246 ///
247 /// # Worst-case complexity
248 /// $T(n, m) = O(m + n \log n \log\log n)$
249 ///
250 /// $M(n, m) = O(m + n \log n)$
251 ///
252 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
253 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
254 ///
255 /// # Examples
256 /// ```
257 /// use malachite_base::num::arithmetic::traits::{AddMulShlAssign, Pow};
258 /// use malachite_nz::integer::Integer;
259 ///
260 /// let mut x = Integer::from(10);
261 /// x.add_mul_shl_assign(Integer::from(3), Integer::from(4), 2);
262 /// assert_eq!(x, 58);
263 ///
264 /// let mut x = Integer::from(-10);
265 /// x.add_mul_shl_assign(Integer::from(3), Integer::from(-4), 2);
266 /// assert_eq!(x, -58);
267 ///
268 /// let mut x = Integer::from(10u32).pow(12);
269 /// x.add_mul_shl_assign(Integer::from(0x10000), -Integer::from(10u32).pow(12), 3);
270 /// assert_eq!(x, -524287000000000000i64);
271 /// ```
272 fn add_mul_shl_assign(&mut self, mut y: Self, z: Self, bits: u64) {
273 if bits == 0 {
274 self.add_mul_assign(y, z);
275 } else {
276 y *= z;
277 y <<= bits;
278 *self += y;
279 }
280 }
281}
282
283impl<'b> AddMulShlAssign<Self, &'b Self> for Integer {
284 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`, in
285 /// place, taking the first [`Integer`] on the right-hand side by value and the second by
286 /// reference.
287 ///
288 /// $x \gets x + yz2^k$.
289 ///
290 /// # Worst-case complexity
291 /// $T(n, m) = O(m + n \log n \log\log n)$
292 ///
293 /// $M(n, m) = O(m + n \log n)$
294 ///
295 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
296 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
297 ///
298 /// # Examples
299 /// ```
300 /// use malachite_base::num::arithmetic::traits::{AddMulShlAssign, Pow};
301 /// use malachite_nz::integer::Integer;
302 ///
303 /// let mut x = Integer::from(10);
304 /// x.add_mul_shl_assign(Integer::from(3), &Integer::from(4), 2);
305 /// assert_eq!(x, 58);
306 ///
307 /// let mut x = Integer::from(-10);
308 /// x.add_mul_shl_assign(Integer::from(3), &Integer::from(-4), 2);
309 /// assert_eq!(x, -58);
310 ///
311 /// let mut x = Integer::from(10u32).pow(12);
312 /// x.add_mul_shl_assign(Integer::from(0x10000), &-Integer::from(10u32).pow(12), 3);
313 /// assert_eq!(x, -524287000000000000i64);
314 /// ```
315 fn add_mul_shl_assign(&mut self, mut y: Self, z: &'b Self, bits: u64) {
316 if bits == 0 {
317 self.add_mul_assign(y, z);
318 } else {
319 y *= z;
320 y <<= bits;
321 *self += y;
322 }
323 }
324}
325
326impl<'a> AddMulShlAssign<&'a Self, Self> for Integer {
327 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`, in
328 /// place, taking the first [`Integer`] on the right-hand side by reference and the second by
329 /// value.
330 ///
331 /// $x \gets x + yz2^k$.
332 ///
333 /// # Worst-case complexity
334 /// $T(n, m) = O(m + n \log n \log\log n)$
335 ///
336 /// $M(n, m) = O(m + n \log n)$
337 ///
338 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
339 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
340 ///
341 /// # Examples
342 /// ```
343 /// use malachite_base::num::arithmetic::traits::{AddMulShlAssign, Pow};
344 /// use malachite_nz::integer::Integer;
345 ///
346 /// let mut x = Integer::from(10);
347 /// x.add_mul_shl_assign(&Integer::from(3), Integer::from(4), 2);
348 /// assert_eq!(x, 58);
349 ///
350 /// let mut x = Integer::from(-10);
351 /// x.add_mul_shl_assign(&Integer::from(3), Integer::from(-4), 2);
352 /// assert_eq!(x, -58);
353 ///
354 /// let mut x = Integer::from(10u32).pow(12);
355 /// x.add_mul_shl_assign(&Integer::from(0x10000), -Integer::from(10u32).pow(12), 3);
356 /// assert_eq!(x, -524287000000000000i64);
357 /// ```
358 fn add_mul_shl_assign(&mut self, y: &'a Self, mut z: Self, bits: u64) {
359 if bits == 0 {
360 self.add_mul_assign(y, z);
361 } else {
362 z *= y;
363 z <<= bits;
364 *self += z;
365 }
366 }
367}
368
369impl<'a, 'b> AddMulShlAssign<&'a Self, &'b Self> for Integer {
370 /// Adds an [`Integer`] and the product of two other [`Integer`]s, shifted left by `bits`, in
371 /// place, taking both [`Integer`]s on the right-hand side by reference.
372 ///
373 /// $x \gets x + yz2^k$.
374 ///
375 /// # Worst-case complexity
376 /// $T(n, m) = O(m + n \log n \log\log n)$
377 ///
378 /// $M(n, m) = O(m + n \log n)$
379 ///
380 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
381 /// z.significant_bits())`, and $m$ is `max(self.significant_bits(), bits)`.
382 ///
383 /// # Examples
384 /// ```
385 /// use malachite_base::num::arithmetic::traits::{AddMulShlAssign, Pow};
386 /// use malachite_nz::integer::Integer;
387 ///
388 /// let mut x = Integer::from(10);
389 /// x.add_mul_shl_assign(&Integer::from(3), &Integer::from(4), 2);
390 /// assert_eq!(x, 58);
391 ///
392 /// let mut x = Integer::from(-10);
393 /// x.add_mul_shl_assign(&Integer::from(3), &Integer::from(-4), 2);
394 /// assert_eq!(x, -58);
395 ///
396 /// let mut x = Integer::from(10u32).pow(12);
397 /// x.add_mul_shl_assign(&Integer::from(0x10000), &-Integer::from(10u32).pow(12), 3);
398 /// assert_eq!(x, -524287000000000000i64);
399 /// ```
400 fn add_mul_shl_assign(&mut self, y: &'a Self, z: &'b Self, bits: u64) {
401 if bits == 0 {
402 self.add_mul_assign(y, z);
403 } else {
404 *self += (y * z) << bits;
405 }
406 }
407}