malachite_q/rational_vector/arithmetic/
canonical_primitive_part.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 crate::rational_vector::arithmetic::content::content_over;
12use malachite_base::num::arithmetic::traits::{
13    CanonicalPrimitivePart, ContentAndCanonicalPrimitivePart,
14};
15use malachite_nz::integer_vector::IntegerVector;
16
17impl CanonicalPrimitivePart for RationalVector {
18    type Output = IntegerVector;
19
20    /// Computes the canonical primitive part of a [`RationalVector`], taking the vector by value.
21    ///
22    /// This is the
23    /// [`primitive_part`](malachite_base::num::arithmetic::traits::PrimitivePart::primitive_part),
24    /// negated if its first nonzero element is negative, so that the first nonzero element is
25    /// positive: the canonical primitive part of the numerators that
26    /// [`to_numerators_and_denominator`](RationalVector::to_numerators_and_denominator) gives. A
27    /// vector and its negation have the same canonical primitive part.
28    ///
29    /// $$
30    /// v = \pm \operatorname{cont}(v) \operatorname{cpp}(v).
31    /// $$
32    ///
33    /// The canonical primitive part of a vector of zeros is a vector of zeros of the same
34    /// dimension.
35    ///
36    /// Taking the vector by value saves nothing, since the numerators are built afresh either way.
37    ///
38    /// # Worst-case complexity
39    /// $T(n, m) = O(mn (\log n)^2 \log\log n)$
40    ///
41    /// $M(n, m) = O(mn)$
42    ///
43    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
44    /// elements' numerators and denominators, and $m$ is the dimension.
45    ///
46    /// # Examples
47    /// ```
48    /// use core::str::FromStr;
49    /// use malachite_base::num::arithmetic::traits::CanonicalPrimitivePart;
50    /// use malachite_q::rational_vector::RationalVector;
51    ///
52    /// let v = RationalVector::from_str("(-1/2, 2/3, -5)").unwrap();
53    /// assert_eq!(v.canonical_primitive_part().to_string(), "(3, -4, 30)");
54    /// ```
55    #[inline]
56    fn canonical_primitive_part(self) -> IntegerVector {
57        self.to_numerators_and_denominator()
58            .0
59            .canonical_primitive_part()
60    }
61}
62
63impl CanonicalPrimitivePart for &RationalVector {
64    type Output = IntegerVector;
65
66    /// Computes the canonical primitive part of a [`RationalVector`], taking the vector by
67    /// reference.
68    ///
69    /// This is the
70    /// [`primitive_part`](malachite_base::num::arithmetic::traits::PrimitivePart::primitive_part),
71    /// negated if its first nonzero element is negative, so that the first nonzero element is
72    /// positive: the canonical primitive part of the numerators that
73    /// [`to_numerators_and_denominator`](RationalVector::to_numerators_and_denominator) gives. A
74    /// vector and its negation have the same canonical primitive part.
75    ///
76    /// $$
77    /// v = \pm \operatorname{cont}(v) \operatorname{cpp}(v).
78    /// $$
79    ///
80    /// The canonical primitive part of a vector of zeros is a vector of zeros of the same
81    /// dimension.
82    ///
83    /// # Worst-case complexity
84    /// $T(n, m) = O(mn (\log n)^2 \log\log n)$
85    ///
86    /// $M(n, m) = O(mn)$
87    ///
88    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
89    /// elements' numerators and denominators, and $m$ is the dimension.
90    ///
91    /// # Examples
92    /// ```
93    /// use core::str::FromStr;
94    /// use malachite_base::num::arithmetic::traits::CanonicalPrimitivePart;
95    /// use malachite_q::rational_vector::RationalVector;
96    ///
97    /// let v = RationalVector::from_str("(-1/2, 2/3, -5)").unwrap();
98    /// assert_eq!((&v).canonical_primitive_part().to_string(), "(3, -4, 30)");
99    /// ```
100    #[inline]
101    fn canonical_primitive_part(self) -> IntegerVector {
102        self.to_numerators_and_denominator()
103            .0
104            .canonical_primitive_part()
105    }
106}
107
108impl ContentAndCanonicalPrimitivePart for RationalVector {
109    type Content = Rational;
110    type CanonicalPrimitivePart = IntegerVector;
111
112    /// Computes the content and the canonical primitive part of a [`RationalVector`] together,
113    /// taking the vector by value.
114    ///
115    /// See [`content`](malachite_base::num::arithmetic::traits::Content::content) and
116    /// [`canonical_primitive_part`](CanonicalPrimitivePart::canonical_primitive_part); the
117    /// numerators are cleared and the content found once rather than twice.
118    ///
119    /// # Worst-case complexity
120    /// $T(n, m) = O(mn (\log n)^2 \log\log n)$
121    ///
122    /// $M(n, m) = O(mn)$
123    ///
124    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
125    /// elements' numerators and denominators, and $m$ is the dimension.
126    ///
127    /// # Examples
128    /// ```
129    /// use core::str::FromStr;
130    /// use malachite_base::num::arithmetic::traits::ContentAndCanonicalPrimitivePart;
131    /// use malachite_q::rational_vector::RationalVector;
132    ///
133    /// let v = RationalVector::from_str("(-1/2, 2/3, -5)").unwrap();
134    /// let (content, primitive_part) = v.content_and_canonical_primitive_part();
135    /// assert_eq!(content.to_string(), "1/6");
136    /// assert_eq!(primitive_part.to_string(), "(3, -4, 30)");
137    /// ```
138    #[inline]
139    fn content_and_canonical_primitive_part(self) -> (Rational, IntegerVector) {
140        let (numerators, denominator) = self.to_numerators_and_denominator();
141        let (content, primitive_part) = numerators.content_and_canonical_primitive_part();
142        (content_over(content, denominator), primitive_part)
143    }
144}
145
146impl ContentAndCanonicalPrimitivePart for &RationalVector {
147    type Content = Rational;
148    type CanonicalPrimitivePart = IntegerVector;
149
150    /// Computes the content and the canonical primitive part of a [`RationalVector`] together,
151    /// taking the vector by reference.
152    ///
153    /// See [`content`](malachite_base::num::arithmetic::traits::Content::content) and
154    /// [`canonical_primitive_part`](CanonicalPrimitivePart::canonical_primitive_part); the
155    /// numerators are cleared and the content found once rather than twice.
156    ///
157    /// # Worst-case complexity
158    /// $T(n, m) = O(mn (\log n)^2 \log\log n)$
159    ///
160    /// $M(n, m) = O(mn)$
161    ///
162    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
163    /// elements' numerators and denominators, and $m$ is the dimension.
164    ///
165    /// # Examples
166    /// ```
167    /// use core::str::FromStr;
168    /// use malachite_base::num::arithmetic::traits::ContentAndCanonicalPrimitivePart;
169    /// use malachite_q::rational_vector::RationalVector;
170    ///
171    /// let v = RationalVector::from_str("(-1/2, 2/3, -5)").unwrap();
172    /// let (content, primitive_part) = (&v).content_and_canonical_primitive_part();
173    /// assert_eq!(content.to_string(), "1/6");
174    /// assert_eq!(primitive_part.to_string(), "(3, -4, 30)");
175    /// ```
176    #[inline]
177    fn content_and_canonical_primitive_part(self) -> (Rational, IntegerVector) {
178        let (numerators, denominator) = self.to_numerators_and_denominator();
179        let (content, primitive_part) = numerators.content_and_canonical_primitive_part();
180        (content_over(content, denominator), primitive_part)
181    }
182}
malachite_q/rational_vector/arithmetic/canonical_primitive_part.rs

malachite_q/rational_vector/arithmetic/
canonical_primitive_part.rs
