malachite_q/rational_vector/arithmetic/content_chained.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::{Content, ContentChained, Gcd};
12
13impl ContentChained<Rational> for RationalVector {
14 type Output = Rational;
15
16 /// Computes the GCD of `x` and the elements of a [`RationalVector`], taking the vector by value
17 /// and `x` by value.
18 ///
19 /// The GCD of `x` and the elements of the 0-dimensional vector, or of a vector of zeros, is
20 /// `x`. The computation stops as soon as the GCD reaches 1.
21 ///
22 /// $$
23 /// f(v, x) = \gcd(x, v_0, v_1, \ldots, v_{n-1}),
24 /// $$
25 ///
26 /// where $n$ is the dimension of $v$.
27 ///
28 /// # Worst-case complexity
29 /// $T(n) = O(n (\log n)^2 \log\log n)$
30 ///
31 /// $M(n) = O(n)$
32 ///
33 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
34 /// elements and of `x`.
35 ///
36 /// # Examples
37 /// ```
38 /// use core::str::FromStr;
39 /// use malachite_base::num::arithmetic::traits::ContentChained;
40 /// use malachite_q::Rational;
41 /// use malachite_q::rational_vector::RationalVector;
42 ///
43 /// let v = RationalVector::from_str("(1/2, -3/4)").unwrap();
44 /// assert_eq!(
45 /// v.clone()
46 /// .content_chained(Rational::from_str("1/6").unwrap())
47 /// .to_string(),
48 /// "1/12"
49 /// );
50 /// assert_eq!(
51 /// v.content_chained(Rational::from_str("0").unwrap())
52 /// .to_string(),
53 /// "1/4"
54 /// );
55 /// let v = RationalVector::from_str("()").unwrap();
56 /// assert_eq!(
57 /// v.content_chained(Rational::from_str("1/3").unwrap())
58 /// .to_string(),
59 /// "1/3"
60 /// );
61 /// ```
62 #[inline]
63 fn content_chained(self, x: Rational) -> Rational {
64 self.content().gcd(x)
65 }
66}
67
68impl ContentChained<&Rational> for RationalVector {
69 type Output = Rational;
70
71 /// Computes the GCD of `x` and the elements of a [`RationalVector`], taking the vector by value
72 /// and `x` by reference.
73 ///
74 /// The GCD of `x` and the elements of the 0-dimensional vector, or of a vector of zeros, is
75 /// `x`. The computation stops as soon as the GCD reaches 1.
76 ///
77 /// $$
78 /// f(v, x) = \gcd(x, v_0, v_1, \ldots, v_{n-1}),
79 /// $$
80 ///
81 /// where $n$ is the dimension of $v$.
82 ///
83 /// # Worst-case complexity
84 /// $T(n) = O(n (\log n)^2 \log\log n)$
85 ///
86 /// $M(n) = O(n)$
87 ///
88 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
89 /// elements and of `x`.
90 ///
91 /// # Examples
92 /// ```
93 /// use core::str::FromStr;
94 /// use malachite_base::num::arithmetic::traits::ContentChained;
95 /// use malachite_q::Rational;
96 /// use malachite_q::rational_vector::RationalVector;
97 ///
98 /// let v = RationalVector::from_str("(1/2, -3/4)").unwrap();
99 /// assert_eq!(
100 /// v.clone()
101 /// .content_chained(&Rational::from_str("1/6").unwrap())
102 /// .to_string(),
103 /// "1/12"
104 /// );
105 /// assert_eq!(
106 /// v.content_chained(&Rational::from_str("0").unwrap())
107 /// .to_string(),
108 /// "1/4"
109 /// );
110 /// let v = RationalVector::from_str("()").unwrap();
111 /// assert_eq!(
112 /// v.content_chained(&Rational::from_str("1/3").unwrap())
113 /// .to_string(),
114 /// "1/3"
115 /// );
116 /// ```
117 #[inline]
118 fn content_chained(self, x: &Rational) -> Rational {
119 self.content().gcd(x)
120 }
121}
122
123impl ContentChained<Rational> for &RationalVector {
124 type Output = Rational;
125
126 /// Computes the GCD of `x` and the elements of a [`RationalVector`], taking the vector by
127 /// reference and `x` by value.
128 ///
129 /// The GCD of `x` and the elements of the 0-dimensional vector, or of a vector of zeros, is
130 /// `x`. The computation stops as soon as the GCD reaches 1.
131 ///
132 /// $$
133 /// f(v, x) = \gcd(x, v_0, v_1, \ldots, v_{n-1}),
134 /// $$
135 ///
136 /// where $n$ is the dimension of $v$.
137 ///
138 /// # Worst-case complexity
139 /// $T(n) = O(n (\log n)^2 \log\log n)$
140 ///
141 /// $M(n) = O(n)$
142 ///
143 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
144 /// elements and of `x`.
145 ///
146 /// # Examples
147 /// ```
148 /// use core::str::FromStr;
149 /// use malachite_base::num::arithmetic::traits::ContentChained;
150 /// use malachite_q::Rational;
151 /// use malachite_q::rational_vector::RationalVector;
152 ///
153 /// let v = RationalVector::from_str("(1/2, -3/4)").unwrap();
154 /// assert_eq!(
155 /// (&v).content_chained(Rational::from_str("1/6").unwrap())
156 /// .to_string(),
157 /// "1/12"
158 /// );
159 /// assert_eq!(
160 /// (&v).content_chained(Rational::from_str("0").unwrap())
161 /// .to_string(),
162 /// "1/4"
163 /// );
164 /// let v = RationalVector::from_str("()").unwrap();
165 /// assert_eq!(
166 /// (&v).content_chained(Rational::from_str("1/3").unwrap())
167 /// .to_string(),
168 /// "1/3"
169 /// );
170 /// ```
171 #[inline]
172 fn content_chained(self, x: Rational) -> Rational {
173 self.content().gcd(x)
174 }
175}
176
177impl ContentChained<&Rational> for &RationalVector {
178 type Output = Rational;
179
180 /// Computes the GCD of `x` and the elements of a [`RationalVector`], taking the vector by
181 /// reference and `x` by reference.
182 ///
183 /// The GCD of `x` and the elements of the 0-dimensional vector, or of a vector of zeros, is
184 /// `x`. The computation stops as soon as the GCD reaches 1.
185 ///
186 /// $$
187 /// f(v, x) = \gcd(x, v_0, v_1, \ldots, v_{n-1}),
188 /// $$
189 ///
190 /// where $n$ is the dimension of $v$.
191 ///
192 /// # Worst-case complexity
193 /// $T(n) = O(n (\log n)^2 \log\log n)$
194 ///
195 /// $M(n) = O(n)$
196 ///
197 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
198 /// elements and of `x`.
199 ///
200 /// # Examples
201 /// ```
202 /// use core::str::FromStr;
203 /// use malachite_base::num::arithmetic::traits::ContentChained;
204 /// use malachite_q::Rational;
205 /// use malachite_q::rational_vector::RationalVector;
206 ///
207 /// let v = RationalVector::from_str("(1/2, -3/4)").unwrap();
208 /// assert_eq!(
209 /// (&v).content_chained(&Rational::from_str("1/6").unwrap())
210 /// .to_string(),
211 /// "1/12"
212 /// );
213 /// assert_eq!(
214 /// (&v).content_chained(&Rational::from_str("0").unwrap())
215 /// .to_string(),
216 /// "1/4"
217 /// );
218 /// let v = RationalVector::from_str("()").unwrap();
219 /// assert_eq!(
220 /// (&v).content_chained(&Rational::from_str("1/3").unwrap())
221 /// .to_string(),
222 /// "1/3"
223 /// );
224 /// ```
225 #[inline]
226 fn content_chained(self, x: &Rational) -> Rational {
227 self.content().gcd(x)
228 }
229}