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