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    ) -> Self {
69        if let Some(log_base) = base.checked_log_base_2() {
70            return Self::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 = Self::from(Natural::from_digits_asc(base, before_point.into_iter()).unwrap());
78        floor
79            + if r == 0u32 {
80                Self::from_naturals(nr, base.pow(nr_len))
81            } else {
82                (Self::from_naturals(r, base.pow(r_len) - Natural::ONE) + Self::from(nr))
83                    / Self::from(base.pow(nr_len))
84            }
85    }
86
87    /// Converts base-$b$ digits to a [`Rational`]. The inputs are taken by reference.
88    ///
89    /// The input consists of the digits of the integer portion of the [`Rational`] and the digits
90    /// of the fractional portion. The integer-portion digits are ordered from least- to
91    /// most-significant, and the fractional-portion digits from most- to least.
92    ///
93    /// The fractional-portion digits may end in infinitely many zeros or $(b-1)$s; these are
94    /// handled correctly.
95    ///
96    /// # Worst-case complexity
97    /// $T(n, m) = O(nm \log (nm)^2 \log\log (nm))$
98    ///
99    /// $M(n, m) = O(nm \log (nm))$
100    ///
101    /// where $T$ is time, $M$ is additional memory, $n$ is `max(before_point.len(),
102    /// after_point.component_len())`, and $m$ is `base.significant_bits()`.
103    ///
104    /// # Panics
105    /// Panics if `base` is less than 2.
106    ///
107    /// # Examples
108    /// ```
109    /// use malachite_base::rational_sequences::RationalSequence;
110    /// use malachite_base::vecs::vec_from_str;
111    /// use malachite_nz::natural::Natural;
112    /// use malachite_q::Rational;
113    ///
114    /// let before_point = vec_from_str("[3]").unwrap();
115    /// let after_point =
116    ///     RationalSequence::from_vecs(Vec::new(), vec_from_str("[1, 4, 2, 8, 5, 7]").unwrap());
117    /// assert_eq!(
118    ///     Rational::from_digits_ref(&Natural::from(10u32), &before_point, &after_point)
119    ///         .to_string(),
120    ///     "22/7"
121    /// );
122    ///
123    /// // 21.34565656...
124    /// let before_point = vec_from_str("[1, 2]").unwrap();
125    /// let after_point = RationalSequence::from_vecs(
126    ///     vec_from_str("[3, 4]").unwrap(),
127    ///     vec_from_str("[5, 6]").unwrap(),
128    /// );
129    /// assert_eq!(
130    ///     Rational::from_digits_ref(&Natural::from(10u32), &before_point, &after_point)
131    ///         .to_string(),
132    ///     "105661/4950"
133    /// );
134    /// ```
135    pub fn from_digits_ref(
136        base: &Natural,
137        before_point: &[Natural],
138        after_point: &RationalSequence<Natural>,
139    ) -> Self {
140        if let Some(log_base) = base.checked_log_base_2() {
141            return Self::from_power_of_2_digits_ref(log_base, before_point, after_point);
142        }
143        let (non_repeating, repeating) = after_point.to_vecs();
144        let r_len = u64::exact_from(repeating.len());
145        let nr_len = u64::exact_from(non_repeating.len());
146        let nr = Natural::from_digits_asc(base, non_repeating.into_iter().rev()).unwrap();
147        let r = Natural::from_digits_asc(base, repeating.into_iter().rev()).unwrap();
148        let floor =
149            Self::from(Natural::from_digits_asc(base, before_point.iter().cloned()).unwrap());
150        floor
151            + if r == 0u32 {
152                Self::from_naturals(nr, base.pow(nr_len))
153            } else {
154                (Self::from_naturals(r, base.pow(r_len) - Natural::ONE) + Self::from(nr))
155                    / Self::from(base.pow(nr_len))
156            }
157    }
158}
malachite_q/conversion/digits/from_digits.rs

malachite_q/conversion/digits/
from_digits.rs
