malachite_nz/integer_vector/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 crate::integer_vector::IntegerVector;
11use crate::natural::Natural;
12use malachite_base::num::arithmetic::traits::{AddMulAssign, AddMulShl, AddMulShlAssign};
13use malachite_base::num::basic::traits::{One, Zero};
14
15fn assert_same_dimension(v: &IntegerVector, w: &IntegerVector) {
16 assert_eq!(
17 v.elements.len(),
18 w.elements.len(),
19 "cannot add-multiply vectors of different dimensions"
20 );
21}
22
23impl AddMulShl<Self, Integer> for IntegerVector {
24 type Output = Self;
25
26 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
27 /// [`IntegerVector`], taking both vectors and the scalar by value.
28 ///
29 /// The operation is taken element by element, so the result has the same dimension as the
30 /// vectors. Like FLINT's, this special-cases multiplication by 0, 1, and $-1$, and a shift by
31 /// 0.
32 ///
33 /// $$
34 /// f(v, w, c, k) = v + cw2^k.
35 /// $$
36 ///
37 /// # Worst-case complexity
38 /// $T(n, m) = O(m + n \log n \log\log n)$
39 ///
40 /// $M(n, m) = O(m + n \log n)$
41 ///
42 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
43 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
44 /// times `self.dimension()`.
45 ///
46 /// # Panics
47 /// Panics if `self` and `w` have different dimensions.
48 ///
49 /// # Examples
50 /// ```
51 /// use core::str::FromStr;
52 /// use malachite_base::num::arithmetic::traits::AddMulShl;
53 /// use malachite_nz::integer::Integer;
54 /// use malachite_nz::integer_vector::IntegerVector;
55 ///
56 /// let v = IntegerVector::from_str("(1, -2, 3)").unwrap();
57 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
58 /// assert_eq!(
59 /// v.add_mul_shl(w, Integer::from(10), 2).to_string(),
60 /// "(161, 198, -237)"
61 /// );
62 ///
63 /// let v = IntegerVector::from_str("(1, 0)").unwrap();
64 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
65 /// assert_eq!(
66 /// v.add_mul_shl(w, Integer::from_str("18446744073709551617").unwrap(), 3)
67 /// .to_string(),
68 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
69 /// );
70 /// ```
71 ///
72 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
73 /// 3.6.0.
74 #[inline]
75 fn add_mul_shl(mut self, w: Self, c: Integer, bits: u64) -> Self {
76 self.add_mul_shl_assign(w, c, bits);
77 self
78 }
79}
80
81impl AddMulShl<Self, &Integer> for IntegerVector {
82 type Output = Self;
83
84 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
85 /// [`IntegerVector`], taking the first vector by value, the second by value, and the scalar by
86 /// reference.
87 ///
88 /// See the documentation for the [`AddMulShl`] implementation that takes everything by value
89 /// for details.
90 ///
91 /// # Worst-case complexity
92 /// $T(n, m) = O(m + n \log n \log\log n)$
93 ///
94 /// $M(n, m) = O(m + n \log n)$
95 ///
96 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
97 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
98 /// times `self.dimension()`.
99 ///
100 /// # Panics
101 /// Panics if `self` and `w` have different dimensions.
102 ///
103 /// # Examples
104 /// ```
105 /// use core::str::FromStr;
106 /// use malachite_base::num::arithmetic::traits::AddMulShl;
107 /// use malachite_nz::integer::Integer;
108 /// use malachite_nz::integer_vector::IntegerVector;
109 ///
110 /// let v = IntegerVector::from_str("(1, -2, 3)").unwrap();
111 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
112 /// assert_eq!(
113 /// v.add_mul_shl(w, &Integer::from(10), 2).to_string(),
114 /// "(161, 198, -237)"
115 /// );
116 ///
117 /// let v = IntegerVector::from_str("(1, 0)").unwrap();
118 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
119 /// assert_eq!(
120 /// v.add_mul_shl(w, &Integer::from_str("18446744073709551617").unwrap(), 3)
121 /// .to_string(),
122 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
123 /// );
124 /// ```
125 ///
126 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
127 /// 3.6.0.
128 #[inline]
129 fn add_mul_shl(mut self, w: Self, c: &Integer, bits: u64) -> Self {
130 self.add_mul_shl_assign(w, c, bits);
131 self
132 }
133}
134
135impl AddMulShl<&Self, Integer> for IntegerVector {
136 type Output = Self;
137
138 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
139 /// [`IntegerVector`], taking the first vector by value, the second by reference, and the scalar
140 /// by value.
141 ///
142 /// See the documentation for the [`AddMulShl`] implementation that takes everything by value
143 /// for details.
144 ///
145 /// # Worst-case complexity
146 /// $T(n, m) = O(m + n \log n \log\log n)$
147 ///
148 /// $M(n, m) = O(m + n \log n)$
149 ///
150 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
151 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
152 /// times `self.dimension()`.
153 ///
154 /// # Panics
155 /// Panics if `self` and `w` have different dimensions.
156 ///
157 /// # Examples
158 /// ```
159 /// use core::str::FromStr;
160 /// use malachite_base::num::arithmetic::traits::AddMulShl;
161 /// use malachite_nz::integer::Integer;
162 /// use malachite_nz::integer_vector::IntegerVector;
163 ///
164 /// let v = IntegerVector::from_str("(1, -2, 3)").unwrap();
165 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
166 /// assert_eq!(
167 /// v.add_mul_shl(&w, Integer::from(10), 2).to_string(),
168 /// "(161, 198, -237)"
169 /// );
170 ///
171 /// let v = IntegerVector::from_str("(1, 0)").unwrap();
172 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
173 /// assert_eq!(
174 /// v.add_mul_shl(&w, Integer::from_str("18446744073709551617").unwrap(), 3)
175 /// .to_string(),
176 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
177 /// );
178 /// ```
179 ///
180 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
181 /// 3.6.0.
182 #[inline]
183 fn add_mul_shl(mut self, w: &Self, c: Integer, bits: u64) -> Self {
184 self.add_mul_shl_assign(w, c, bits);
185 self
186 }
187}
188
189impl AddMulShl<&Self, &Integer> for IntegerVector {
190 type Output = Self;
191
192 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
193 /// [`IntegerVector`], taking the first vector by value, the second by reference, and the scalar
194 /// by reference.
195 ///
196 /// See the documentation for the [`AddMulShl`] implementation that takes everything by value
197 /// for details.
198 ///
199 /// # Worst-case complexity
200 /// $T(n, m) = O(m + n \log n \log\log n)$
201 ///
202 /// $M(n, m) = O(m + n \log n)$
203 ///
204 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
205 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
206 /// times `self.dimension()`.
207 ///
208 /// # Panics
209 /// Panics if `self` and `w` have different dimensions.
210 ///
211 /// # Examples
212 /// ```
213 /// use core::str::FromStr;
214 /// use malachite_base::num::arithmetic::traits::AddMulShl;
215 /// use malachite_nz::integer::Integer;
216 /// use malachite_nz::integer_vector::IntegerVector;
217 ///
218 /// let v = IntegerVector::from_str("(1, -2, 3)").unwrap();
219 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
220 /// assert_eq!(
221 /// v.add_mul_shl(&w, &Integer::from(10), 2).to_string(),
222 /// "(161, 198, -237)"
223 /// );
224 ///
225 /// let v = IntegerVector::from_str("(1, 0)").unwrap();
226 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
227 /// assert_eq!(
228 /// v.add_mul_shl(&w, &Integer::from_str("18446744073709551617").unwrap(), 3)
229 /// .to_string(),
230 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
231 /// );
232 /// ```
233 ///
234 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
235 /// 3.6.0.
236 #[inline]
237 fn add_mul_shl(mut self, w: &Self, c: &Integer, bits: u64) -> Self {
238 self.add_mul_shl_assign(w, c, bits);
239 self
240 }
241}
242
243impl AddMulShl<&IntegerVector, &Integer> for &IntegerVector {
244 type Output = IntegerVector;
245
246 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
247 /// [`IntegerVector`], taking both vectors and the scalar by reference.
248 ///
249 /// See the documentation for the [`AddMulShl`] implementation that takes everything by value
250 /// for details.
251 ///
252 /// # Worst-case complexity
253 /// $T(n, m) = O(m + n \log n \log\log n)$
254 ///
255 /// $M(n, m) = O(m + n \log n)$
256 ///
257 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
258 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
259 /// times `self.dimension()`.
260 ///
261 /// # Panics
262 /// Panics if `self` and `w` have different dimensions.
263 ///
264 /// # Examples
265 /// ```
266 /// use core::str::FromStr;
267 /// use malachite_base::num::arithmetic::traits::AddMulShl;
268 /// use malachite_nz::integer::Integer;
269 /// use malachite_nz::integer_vector::IntegerVector;
270 ///
271 /// let v = IntegerVector::from_str("(1, -2, 3)").unwrap();
272 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
273 /// assert_eq!(
274 /// (&v).add_mul_shl(&w, &Integer::from(10), 2).to_string(),
275 /// "(161, 198, -237)"
276 /// );
277 ///
278 /// let v = IntegerVector::from_str("(1, 0)").unwrap();
279 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
280 /// assert_eq!(
281 /// (&v).add_mul_shl(&w, &Integer::from_str("18446744073709551617").unwrap(), 3)
282 /// .to_string(),
283 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
284 /// );
285 /// ```
286 ///
287 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
288 /// 3.6.0.
289 fn add_mul_shl(self, w: &IntegerVector, c: &Integer, bits: u64) -> IntegerVector {
290 let mut v = self.clone();
291 v.add_mul_shl_assign(w, c, bits);
292 v
293 }
294}
295
296impl AddMulShlAssign<Self, Integer> for IntegerVector {
297 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
298 /// [`IntegerVector`], in place, taking the vector and the scalar on the right-hand side by
299 /// value.
300 ///
301 /// See the documentation for the [`AddMulShl`] implementation that takes everything by value
302 /// for details.
303 ///
304 /// # Worst-case complexity
305 /// $T(n, m) = O(m + n \log n \log\log n)$
306 ///
307 /// $M(n, m) = O(m + n \log n)$
308 ///
309 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
310 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
311 /// times `self.dimension()`.
312 ///
313 /// # Panics
314 /// Panics if `self` and `w` have different dimensions.
315 ///
316 /// # Examples
317 /// ```
318 /// use core::str::FromStr;
319 /// use malachite_base::num::arithmetic::traits::AddMulShlAssign;
320 /// use malachite_nz::integer::Integer;
321 /// use malachite_nz::integer_vector::IntegerVector;
322 ///
323 /// let mut v = IntegerVector::from_str("(1, -2, 3)").unwrap();
324 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
325 /// v.add_mul_shl_assign(w, Integer::from(10), 2);
326 /// assert_eq!(v.to_string(), "(161, 198, -237)");
327 ///
328 /// let mut v = IntegerVector::from_str("(1, 0)").unwrap();
329 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
330 /// v.add_mul_shl_assign(w, Integer::from_str("18446744073709551617").unwrap(), 3);
331 /// assert_eq!(
332 /// v.to_string(),
333 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
334 /// );
335 /// ```
336 ///
337 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
338 /// 3.6.0.
339 #[inline]
340 fn add_mul_shl_assign(&mut self, w: Self, c: Integer, bits: u64) {
341 self.add_mul_shl_assign(w, &c, bits);
342 }
343}
344
345impl AddMulShlAssign<Self, &Integer> for IntegerVector {
346 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
347 /// [`IntegerVector`], in place, taking the vector on the right-hand side by value and the
348 /// scalar by reference.
349 ///
350 /// See the documentation for the [`AddMulShl`] implementation that takes everything by value
351 /// for details.
352 ///
353 /// # Worst-case complexity
354 /// $T(n, m) = O(m + n \log n \log\log n)$
355 ///
356 /// $M(n, m) = O(m + n \log n)$
357 ///
358 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
359 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
360 /// times `self.dimension()`.
361 ///
362 /// # Panics
363 /// Panics if `self` and `w` have different dimensions.
364 ///
365 /// # Examples
366 /// ```
367 /// use core::str::FromStr;
368 /// use malachite_base::num::arithmetic::traits::AddMulShlAssign;
369 /// use malachite_nz::integer::Integer;
370 /// use malachite_nz::integer_vector::IntegerVector;
371 ///
372 /// let mut v = IntegerVector::from_str("(1, -2, 3)").unwrap();
373 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
374 /// v.add_mul_shl_assign(w, &Integer::from(10), 2);
375 /// assert_eq!(v.to_string(), "(161, 198, -237)");
376 ///
377 /// let mut v = IntegerVector::from_str("(1, 0)").unwrap();
378 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
379 /// v.add_mul_shl_assign(w, &Integer::from_str("18446744073709551617").unwrap(), 3);
380 /// assert_eq!(
381 /// v.to_string(),
382 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
383 /// );
384 /// ```
385 ///
386 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
387 /// 3.6.0.
388 fn add_mul_shl_assign(&mut self, w: Self, c: &Integer, bits: u64) {
389 assert_same_dimension(self, &w);
390 if bits == 0 {
391 self.add_mul_assign(w, c);
392 return;
393 }
394 match *c {
395 integer_zero!() => {}
396 integer_one!() => {
397 for (x, mut y) in self.elements.iter_mut().zip(w.elements) {
398 y <<= bits;
399 *x += y;
400 }
401 }
402 integer_negative_one!() => {
403 for (x, mut y) in self.elements.iter_mut().zip(w.elements) {
404 y <<= bits;
405 *x -= y;
406 }
407 }
408 _ => {
409 for (x, y) in self.elements.iter_mut().zip(w.elements) {
410 x.add_mul_shl_assign(y, c, bits);
411 }
412 }
413 }
414 }
415}
416
417impl AddMulShlAssign<&Self, Integer> for IntegerVector {
418 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
419 /// [`IntegerVector`], in place, taking the vector on the right-hand side by reference and the
420 /// scalar by value.
421 ///
422 /// See the documentation for the [`AddMulShl`] implementation that takes everything by value
423 /// for details.
424 ///
425 /// # Worst-case complexity
426 /// $T(n, m) = O(m + n \log n \log\log n)$
427 ///
428 /// $M(n, m) = O(m + n \log n)$
429 ///
430 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
431 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
432 /// times `self.dimension()`.
433 ///
434 /// # Panics
435 /// Panics if `self` and `w` have different dimensions.
436 ///
437 /// # Examples
438 /// ```
439 /// use core::str::FromStr;
440 /// use malachite_base::num::arithmetic::traits::AddMulShlAssign;
441 /// use malachite_nz::integer::Integer;
442 /// use malachite_nz::integer_vector::IntegerVector;
443 ///
444 /// let mut v = IntegerVector::from_str("(1, -2, 3)").unwrap();
445 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
446 /// v.add_mul_shl_assign(&w, Integer::from(10), 2);
447 /// assert_eq!(v.to_string(), "(161, 198, -237)");
448 ///
449 /// let mut v = IntegerVector::from_str("(1, 0)").unwrap();
450 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
451 /// v.add_mul_shl_assign(&w, Integer::from_str("18446744073709551617").unwrap(), 3);
452 /// assert_eq!(
453 /// v.to_string(),
454 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
455 /// );
456 /// ```
457 ///
458 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
459 /// 3.6.0.
460 #[inline]
461 fn add_mul_shl_assign(&mut self, w: &Self, c: Integer, bits: u64) {
462 self.add_mul_shl_assign(w, &c, bits);
463 }
464}
465
466impl AddMulShlAssign<&Self, &Integer> for IntegerVector {
467 /// Adds a scalar multiple of an [`IntegerVector`], shifted left by `bits`, to an
468 /// [`IntegerVector`], in place, taking the vector and the scalar on the right-hand side by
469 /// reference.
470 ///
471 /// See the documentation for the [`AddMulShl`] implementation that takes everything by value
472 /// for details.
473 ///
474 /// # Worst-case complexity
475 /// $T(n, m) = O(m + n \log n \log\log n)$
476 ///
477 /// $M(n, m) = O(m + n \log n)$
478 ///
479 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the elements
480 /// of `w` and of `c`, and $m$ is the total number of bits of the elements of `self` plus `bits`
481 /// times `self.dimension()`.
482 ///
483 /// # Panics
484 /// Panics if `self` and `w` have different dimensions.
485 ///
486 /// # Examples
487 /// ```
488 /// use core::str::FromStr;
489 /// use malachite_base::num::arithmetic::traits::AddMulShlAssign;
490 /// use malachite_nz::integer::Integer;
491 /// use malachite_nz::integer_vector::IntegerVector;
492 ///
493 /// let mut v = IntegerVector::from_str("(1, -2, 3)").unwrap();
494 /// let w = IntegerVector::from_str("(4, 5, -6)").unwrap();
495 /// v.add_mul_shl_assign(&w, &Integer::from(10), 2);
496 /// assert_eq!(v.to_string(), "(161, 198, -237)");
497 ///
498 /// let mut v = IntegerVector::from_str("(1, 0)").unwrap();
499 /// let w = IntegerVector::from_str("(18446744073709551615, -1)").unwrap();
500 /// v.add_mul_shl_assign(&w, &Integer::from_str("18446744073709551617").unwrap(), 3);
501 /// assert_eq!(
502 /// v.to_string(),
503 /// "(2722258935367507707706996859454145691641, -147573952589676412936)"
504 /// );
505 /// ```
506 ///
507 /// This is equivalent to `_fmpz_vec_scalar_addmul_si_2exp` from `fmpz_vec/scalar.c`, FLINT
508 /// 3.6.0.
509 fn add_mul_shl_assign(&mut self, w: &Self, c: &Integer, bits: u64) {
510 assert_same_dimension(self, w);
511 if bits == 0 {
512 self.add_mul_assign(w, c);
513 return;
514 }
515 match *c {
516 integer_zero!() => {}
517 integer_one!() => {
518 for (x, y) in self.elements.iter_mut().zip(&w.elements) {
519 *x += y << bits;
520 }
521 }
522 integer_negative_one!() => {
523 for (x, y) in self.elements.iter_mut().zip(&w.elements) {
524 *x -= y << bits;
525 }
526 }
527 _ => {
528 for (x, y) in self.elements.iter_mut().zip(&w.elements) {
529 x.add_mul_shl_assign(y, c, bits);
530 }
531 }
532 }
533 }
534}