malachite_q/conversion/continued_fraction/from_continued_fraction.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::Rational;
10use core::mem::swap;
11use malachite_base::num::arithmetic::traits::{AddMulAssign, UnsignedAbs};
12use malachite_base::num::basic::traits::{One, Zero};
13use malachite_nz::integer::Integer;
14use malachite_nz::natural::Natural;
15
16impl Rational {
17 /// Converts a finite continued fraction to a [`Rational`], taking the inputs by value.
18 ///
19 /// The input has two components. The first is the first value of the continued fraction, which
20 /// may be any [`Integer`] and is equal to the floor of the [`Rational`]. The second is an
21 /// iterator of the remaining values, which must all be positive. Using the standard notation
22 /// for continued fractions, the first value is the number before the semicolon, and the second
23 /// value contains the remaining numbers.
24 ///
25 /// Each rational number has two continued fraction representations. Either one is a valid
26 /// input.
27 ///
28 /// $f(a_0, (a_1, a_2, a_3, \ldots)) = [a_0; a_1, a_2, a_3, \ldots]$.
29 ///
30 /// # Worst-case complexity
31 /// $T(n, m) = O((nm)^2 \log (nm) \log\log (nm))$
32 ///
33 /// $M(n, m) = O(nm \log (nm))$
34 ///
35 /// where $T$ is time, $M$ is additional memory, $n$ is `max(floor.significant_bits(),
36 /// xs.map(Natural::significant_bits).max())`, and $m$ is `xs.count()`.
37 ///
38 /// # Panics
39 /// Panics if any [`Natural`] in `xs` is zero.
40 ///
41 /// # Examples
42 /// ```
43 /// use malachite_base::num::basic::traits::Zero;
44 /// use malachite_base::vecs::vec_from_str;
45 /// use malachite_nz::integer::Integer;
46 /// use malachite_q::Rational;
47 ///
48 /// let xs = vec_from_str("[1, 2]").unwrap().into_iter();
49 /// assert_eq!(
50 /// Rational::from_continued_fraction(Integer::ZERO, xs).to_string(),
51 /// "2/3"
52 /// );
53 ///
54 /// let xs = vec_from_str("[7, 16]").unwrap().into_iter();
55 /// assert_eq!(
56 /// Rational::from_continued_fraction(Integer::from(3), xs).to_string(),
57 /// "355/113"
58 /// );
59 /// ```
60 pub fn from_continued_fraction<I: Iterator<Item = Natural>>(floor: Integer, xs: I) -> Rational {
61 let mut previous_numerator = Integer::ONE;
62 let mut previous_denominator = Natural::ZERO;
63 let mut numerator = floor;
64 let mut denominator = Natural::ONE;
65 for n in xs {
66 assert_ne!(n, 0u32);
67 previous_numerator.add_mul_assign(&numerator, Integer::from(&n));
68 previous_denominator.add_mul_assign(&denominator, n);
69 swap(&mut numerator, &mut previous_numerator);
70 swap(&mut denominator, &mut previous_denominator);
71 }
72 Rational {
73 sign: numerator >= 0,
74 numerator: numerator.unsigned_abs(),
75 denominator,
76 }
77 }
78
79 /// Converts a finite continued fraction to a [`Rational`], taking the inputs by reference.
80 ///
81 /// The input has two components. The first is the first value of the continued fraction, which
82 /// may be any [`Integer`] and is equal to the floor of the [`Rational`]. The second is an
83 /// iterator of the remaining values, which must all be positive. Using the standard notation
84 /// for continued fractions, the first value is the number before the semicolon, and the second
85 /// value contains the remaining numbers.
86 ///
87 /// Each rational number has two continued fraction representations. Either one is a valid
88 /// input.
89 ///
90 /// $f(a_0, (a_1, a_2, a_3, \ldots)) = [a_0; a_1, a_2, a_3, \ldots]$.
91 ///
92 /// # Worst-case complexity
93 /// $T(n, m) = O((nm)^2 \log (nm) \log\log (nm))$
94 ///
95 /// $M(n, m) = O(nm \log (nm))$
96 ///
97 /// where $T$ is time, $M$ is additional memory, $n$ is `max(floor.significant_bits(),
98 /// xs.map(Natural::significant_bits).max())`, and $m$ is `xs.count()`.
99 ///
100 /// # Panics
101 /// Panics if any [`Natural`] in `xs` is zero.
102 ///
103 /// # Examples
104 /// ```
105 /// use malachite_base::num::basic::traits::Zero;
106 /// use malachite_base::vecs::vec_from_str;
107 /// use malachite_nz::integer::Integer;
108 /// use malachite_q::Rational;
109 ///
110 /// let xs = vec_from_str("[1, 2]").unwrap();
111 /// assert_eq!(
112 /// Rational::from_continued_fraction_ref(&Integer::ZERO, xs.iter()).to_string(),
113 /// "2/3"
114 /// );
115 ///
116 /// let xs = vec_from_str("[7, 16]").unwrap();
117 /// assert_eq!(
118 /// Rational::from_continued_fraction_ref(&Integer::from(3), xs.iter()).to_string(),
119 /// "355/113"
120 /// );
121 /// ```
122 pub fn from_continued_fraction_ref<'a, I: Iterator<Item = &'a Natural>>(
123 floor: &Integer,
124 xs: I,
125 ) -> Rational {
126 let mut previous_numerator = Integer::ONE;
127 let mut previous_denominator = Natural::ZERO;
128 let mut numerator = floor.clone();
129 let mut denominator = Natural::ONE;
130 for n in xs {
131 assert_ne!(*n, 0u32);
132 previous_numerator.add_mul_assign(&numerator, Integer::from(n));
133 previous_denominator.add_mul_assign(&denominator, n);
134 swap(&mut numerator, &mut previous_numerator);
135 swap(&mut denominator, &mut previous_denominator);
136 }
137 Rational {
138 sign: numerator >= 0,
139 numerator: numerator.unsigned_abs(),
140 denominator,
141 }
142 }
143}