malachite_q/conversion/digits/
from_digits.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 alloc::vec::Vec;
11use malachite_base::num::arithmetic::traits::{CheckedLogBase2, Pow};
12use malachite_base::num::basic::traits::One;
13use malachite_base::num::conversion::traits::{Digits, ExactFrom};
14use malachite_base::rational_sequences::RationalSequence;
15use malachite_nz::natural::Natural;
16
17impl Rational {
18    /// Converts base-$b$ digits to a [`Rational`]. The inputs are taken by value.
19    ///
20    /// The input consists of the digits of the integer portion of the [`Rational`] and the digits
21    /// of the fractional portion. The integer-portion digits are ordered from least- to
22    /// most-significant, and the fractional-portion digits from most- to least.
23    ///
24    /// The fractional-portion digits may end in infinitely many zeros or $(b-1)$s; these are
25    /// handled correctly.
26    ///
27    /// # Worst-case complexity
28    /// $T(n, m) = O(nm \log (nm)^2 \log\log (nm))$
29    ///
30    /// $M(n, m) = O(nm \log (nm))$
31    ///
32    /// where $T$ is time, $M$ is additional memory, $n$ is `max(before_point.len(),
33    /// after_point.component_len())`, and $m$ is `base.significant_bits()`.
34    ///
35    /// # Panics
36    /// Panics if `base` is less than 2.
37    ///
38    /// # Examples
39    /// ```
40    /// use malachite_base::rational_sequences::RationalSequence;
41    /// use malachite_base::vecs::vec_from_str;
42    /// use malachite_nz::natural::Natural;
43    /// use malachite_q::Rational;
44    ///
45    /// let before_point = vec_from_str("[3]").unwrap();
46    /// let after_point =
47    ///     RationalSequence::from_vecs(Vec::new(), vec_from_str("[1, 4, 2, 8, 5, 7]").unwrap());
48    /// assert_eq!(
49    ///     Rational::from_digits(&Natural::from(10u32), before_point, after_point).to_string(),
50    ///     "22/7"
51    /// );
52    ///
53    /// // 21.34565656...
54    /// let before_point = vec_from_str("[1, 2]").unwrap();
55    /// let after_point = RationalSequence::from_vecs(
56    ///     vec_from_str("[3, 4]").unwrap(),
57    ///     vec_from_str("[5, 6]").unwrap(),
58    /// );
59    /// assert_eq!(
60    ///     Rational::from_digits(&Natural::from(10u32), before_point, after_point).to_string(),
61    ///     "105661/4950"
62    /// );
63    /// ```
64    pub fn from_digits(
65        base: &Natural,
66        before_point: Vec<Natural>,
67        after_point: RationalSequence<Natural>,
68    ) -> Rational {
69        if let Some(log_base) = base.checked_log_base_2() {
70            return Rational::from_power_of_2_digits(log_base, before_point, after_point);
71        }
72        let (non_repeating, repeating) = after_point.into_vecs();
73        let r_len = u64::exact_from(repeating.len());
74        let nr_len = u64::exact_from(non_repeating.len());
75        let nr = Natural::from_digits_asc(base, non_repeating.into_iter().rev()).unwrap();
76        let r = Natural::from_digits_asc(base, repeating.into_iter().rev()).unwrap();
77        let floor =
78            Rational::from(Natural::from_digits_asc(base, before_point.into_iter()).unwrap());
79        floor
80            + if r == 0u32 {
81                Rational::from_naturals(nr, base.pow(nr_len))
82            } else {
83                (Rational::from_naturals(r, base.pow(r_len) - Natural::ONE) + Rational::from(nr))
84                    / Rational::from(base.pow(nr_len))
85            }
86    }
87
88    /// Converts base-$b$ digits to a [`Rational`]. The inputs are taken by reference.
89    ///
90    /// The input consists of the digits of the integer portion of the [`Rational`] and the digits
91    /// of the fractional portion. The integer-portion digits are ordered from least- to
92    /// most-significant, and the fractional-portion digits from most- to least.
93    ///
94    /// The fractional-portion digits may end in infinitely many zeros or $(b-1)$s; these are
95    /// handled correctly.
96    ///
97    /// # Worst-case complexity
98    /// $T(n, m) = O(nm \log (nm)^2 \log\log (nm))$
99    ///
100    /// $M(n, m) = O(nm \log (nm))$
101    ///
102    /// where $T$ is time, $M$ is additional memory, $n$ is `max(before_point.len(),
103    /// after_point.component_len())`, and $m$ is `base.significant_bits()`.
104    ///
105    /// # Panics
106    /// Panics if `base` is less than 2.
107    ///
108    /// # Examples
109    /// ```
110    /// use malachite_base::rational_sequences::RationalSequence;
111    /// use malachite_base::vecs::vec_from_str;
112    /// use malachite_nz::natural::Natural;
113    /// use malachite_q::Rational;
114    ///
115    /// let before_point = vec_from_str("[3]").unwrap();
116    /// let after_point =
117    ///     RationalSequence::from_vecs(Vec::new(), vec_from_str("[1, 4, 2, 8, 5, 7]").unwrap());
118    /// assert_eq!(
119    ///     Rational::from_digits_ref(&Natural::from(10u32), &before_point, &after_point)
120    ///         .to_string(),
121    ///     "22/7"
122    /// );
123    ///
124    /// // 21.34565656...
125    /// let before_point = vec_from_str("[1, 2]").unwrap();
126    /// let after_point = RationalSequence::from_vecs(
127    ///     vec_from_str("[3, 4]").unwrap(),
128    ///     vec_from_str("[5, 6]").unwrap(),
129    /// );
130    /// assert_eq!(
131    ///     Rational::from_digits_ref(&Natural::from(10u32), &before_point, &after_point)
132    ///         .to_string(),
133    ///     "105661/4950"
134    /// );
135    /// ```
136    pub fn from_digits_ref(
137        base: &Natural,
138        before_point: &[Natural],
139        after_point: &RationalSequence<Natural>,
140    ) -> Rational {
141        if let Some(log_base) = base.checked_log_base_2() {
142            return Rational::from_power_of_2_digits_ref(log_base, before_point, after_point);
143        }
144        let (non_repeating, repeating) = after_point.to_vecs();
145        let r_len = u64::exact_from(repeating.len());
146        let nr_len = u64::exact_from(non_repeating.len());
147        let nr = Natural::from_digits_asc(base, non_repeating.into_iter().rev()).unwrap();
148        let r = Natural::from_digits_asc(base, repeating.into_iter().rev()).unwrap();
149        let floor =
150            Rational::from(Natural::from_digits_asc(base, before_point.iter().cloned()).unwrap());
151        floor
152            + if r == 0u32 {
153                Rational::from_naturals(nr, base.pow(nr_len))
154            } else {
155                (Rational::from_naturals(r, base.pow(r_len) - Natural::ONE) + Rational::from(nr))
156                    / Rational::from(base.pow(nr_len))
157            }
158    }
159}
malachite_q/conversion/digits/from_digits.rs

malachite_q/conversion/digits/
from_digits.rs
