malachite_q/conversion/continued_fraction/convergents.rs
1// Copyright © 2025 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::conversion::continued_fraction::to_continued_fraction::RationalContinuedFraction;
10use crate::conversion::traits::ContinuedFraction;
11use crate::conversion::traits::Convergents;
12use crate::Rational;
13use core::mem::swap;
14use malachite_base::num::arithmetic::traits::{AddMulAssign, UnsignedAbs};
15use malachite_base::num::basic::traits::{One, Zero};
16use malachite_nz::integer::Integer;
17use malachite_nz::natural::Natural;
18
19/// An iterator that produces the convergents of a [`Rational`].
20///
21/// See [`convergents`](Rational::convergents) for more information.
22#[derive(Clone, Debug, Eq, PartialEq)]
23pub struct RationalConvergents {
24 first: bool,
25 previous_numerator: Integer,
26 previous_denominator: Natural,
27 numerator: Integer,
28 denominator: Natural,
29 cf: RationalContinuedFraction,
30}
31
32impl Iterator for RationalConvergents {
33 type Item = Rational;
34
35 fn next(&mut self) -> Option<Rational> {
36 if self.first {
37 self.first = false;
38 Some(Rational::from(&self.numerator))
39 } else if let Some(n) = self.cf.next() {
40 self.previous_numerator
41 .add_mul_assign(&self.numerator, Integer::from(&n));
42 self.previous_denominator
43 .add_mul_assign(&self.denominator, n);
44 swap(&mut self.numerator, &mut self.previous_numerator);
45 swap(&mut self.denominator, &mut self.previous_denominator);
46 Some(Rational {
47 sign: self.numerator >= 0,
48 numerator: (&self.numerator).unsigned_abs(),
49 denominator: self.denominator.clone(),
50 })
51 } else {
52 None
53 }
54 }
55}
56
57impl Convergents for Rational {
58 type C = RationalConvergents;
59
60 /// Returns the convergents of a [`Rational`], taking the [`Rational`] by value.
61 ///
62 /// The convergents of a number are the sequence of rational numbers whose continued fractions
63 /// are the prefixes of the number's continued fraction. The first convergent is the floor of
64 /// the number. The sequence of convergents is finite iff the number is rational, in which case
65 /// the last convergent is the number itself. Each convergent is closer to the number than the
66 /// previous convergent is. The even-indexed convergents are less than or equal to the number,
67 /// and the odd-indexed ones are greater than or equal to it.
68 ///
69 /// $f(x) = ([a_0; a_1, a_2, \ldots, a_i])_{i=0}^{n}$, where $x = [a_0; a_1, a_2, \ldots, a_n]$
70 /// and $a_n \neq 1$.
71 ///
72 /// The output length is $O(n)$, where $n$ is `self.significant_bits()`.
73 ///
74 /// # Worst-case complexity per iteration
75 /// $T(n) = O(n \log n \log\log n)$
76 ///
77 /// $M(n) = O(n \log n)$
78 ///
79 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
80 ///
81 /// # Examples
82 /// ```
83 /// use itertools::Itertools;
84 /// use malachite_base::strings::ToDebugString;
85 /// use malachite_q::conversion::traits::Convergents;
86 /// use malachite_q::Rational;
87 ///
88 /// assert_eq!(
89 /// Rational::from_signeds(2, 3)
90 /// .convergents()
91 /// .collect_vec()
92 /// .to_debug_string(),
93 /// "[0, 1, 2/3]"
94 /// );
95 /// assert_eq!(
96 /// Rational::from_signeds(355, 113)
97 /// .convergents()
98 /// .collect_vec()
99 /// .to_debug_string(),
100 /// "[3, 22/7, 355/113]",
101 /// );
102 /// ```
103 fn convergents(self) -> RationalConvergents {
104 let (floor, cf) = self.continued_fraction();
105 RationalConvergents {
106 first: true,
107 previous_numerator: Integer::ONE,
108 previous_denominator: Natural::ZERO,
109 numerator: floor,
110 denominator: Natural::ONE,
111 cf,
112 }
113 }
114}
115
116impl Convergents for &Rational {
117 type C = RationalConvergents;
118
119 /// Returns the convergents of a [`Rational`], taking the [`Rational`] by reference.
120 ///
121 /// The convergents of a number are the sequence of rational numbers whose continued fractions
122 /// are the prefixes of the number's continued fraction. The first convergent is the floor of
123 /// the number. The sequence of convergents is finite iff the number is rational, in which case
124 /// the last convergent is the number itself. Each convergent is closer to the number than the
125 /// previous convergent is. The even-indexed convergents are less than or equal to the number,
126 /// and the odd-indexed ones are greater than or equal to it.
127 ///
128 /// $f(x) = ([a_0; a_1, a_2, \ldots, a_i])_{i=0}^{n}$, where $x = [a_0; a_1, a_2, \ldots, a_n]$
129 /// and $a_n \neq 1$.
130 ///
131 /// The output length is $O(n)$, where $n$ is `self.significant_bits()`.
132 ///
133 /// # Worst-case complexity
134 /// $T(n) = O(n \log n \log\log n)$
135 ///
136 /// $M(n) = O(n \log n)$
137 ///
138 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
139 ///
140 /// # Examples
141 /// ```
142 /// use itertools::Itertools;
143 /// use malachite_base::strings::ToDebugString;
144 /// use malachite_q::conversion::traits::Convergents;
145 /// use malachite_q::Rational;
146 ///
147 /// assert_eq!(
148 /// (&Rational::from_signeds(2, 3))
149 /// .convergents()
150 /// .collect_vec()
151 /// .to_debug_string(),
152 /// "[0, 1, 2/3]"
153 /// );
154 /// assert_eq!(
155 /// (&Rational::from_signeds(355, 113))
156 /// .convergents()
157 /// .collect_vec()
158 /// .to_debug_string(),
159 /// "[3, 22/7, 355/113]",
160 /// );
161 /// ```
162 fn convergents(self) -> RationalConvergents {
163 let (floor, cf) = self.continued_fraction();
164 RationalConvergents {
165 first: true,
166 previous_numerator: Integer::ONE,
167 previous_denominator: Natural::ZERO,
168 numerator: floor,
169 denominator: Natural::ONE,
170 cf,
171 }
172 }
173}