malachite_q/conversion/digits/
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 crate::conversion::digits::power_of_2_digits::RationalPowerOf2Digits;
11use alloc::vec::Vec;
12use malachite_base::num::arithmetic::traits::{Abs, CheckedLogBase2, Floor, UnsignedAbs};
13use malachite_base::num::conversion::traits::Digits;
14use malachite_nz::natural::Natural;
15
16#[doc(hidden)]
17#[derive(Clone, Debug, Eq, PartialEq)]
18pub struct RationalGeneralDigits {
19    base: Rational,
20    remainder: Rational,
21}
22
23impl Iterator for RationalGeneralDigits {
24    type Item = Natural;
25
26    fn next(&mut self) -> Option<Natural> {
27        if self.remainder == 0u32 {
28            None
29        } else {
30            self.remainder *= &self.base;
31            let digit = (&self.remainder).floor().unsigned_abs();
32            self.remainder -= Rational::from(&digit);
33            Some(digit)
34        }
35    }
36}
37
38/// Represents the base-$b$ digits of the fractional portion of a [`Rational`] number.
39///
40/// See [`digits`](Rational::digits) for more information.
41#[derive(Clone, Debug, Eq, PartialEq)]
42pub enum RationalDigits {
43    General(RationalGeneralDigits),
44    PowerOf2(RationalPowerOf2Digits),
45}
46
47impl Iterator for RationalDigits {
48    type Item = Natural;
49
50    fn next(&mut self) -> Option<Natural> {
51        match self {
52            Self::General(xs) => xs.next(),
53            Self::PowerOf2(xs) => xs.next(),
54        }
55    }
56}
57
58impl Rational {
59    /// Returns the base-$b$ digits of a [`Rational`].
60    ///
61    /// The output has two components. The first is a [`Vec`] of the digits of the integer portion
62    /// of the [`Rational`], least- to most-significant. The second is an iterator of the digits of
63    /// the fractional portion.
64    ///
65    /// The output is in its simplest form: the integer-portion digits do not end with a zero, and
66    /// the fractional-portion digits do not end with infinitely many zeros or $(b-1)$s.
67    ///
68    /// If the [`Rational`] has a small denominator, it may be more efficient to use
69    /// [`to_digits`](Rational::to_digits) or [`into_digits`](Rational::into_digits) instead. These
70    /// functions compute the entire repeating portion of the repeating digits.
71    ///
72    /// For example, consider these two expressions:
73    /// - `Rational::from_signeds(1, 7).digits(Natural::from(10u32)).1.nth(1000)`
74    /// - `Rational::from_signeds(1, 7).into_digits(Natural::from(10u32)).1[1000]`
75    ///
76    /// Both get the thousandth digit after the decimal point of `1/7`. The first way explicitly
77    /// calculates each digit after the decimal point, whereas the second way determines that `1/7`
78    /// is `0.(142857)`, with the `142857` repeating, and takes `1000 % 6 == 4` to determine that
79    /// the thousandth digit is 5. But when the [`Rational`] has a large denominator, the second way
80    /// is less efficient.
81    ///
82    /// # Worst-case complexity per iteration
83    /// $T(n) = O(n \log n \log\log n)$
84    ///
85    /// $M(n) = O(n \log n)$
86    ///
87    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(self.significant_bits(),
88    /// base.significant_bits())`.
89    ///
90    /// # Panics
91    /// Panics if `base` is less than 2.
92    ///
93    /// # Examples
94    /// ```
95    /// use malachite_base::iterators::prefix_to_string;
96    /// use malachite_base::strings::ToDebugString;
97    /// use malachite_nz::natural::Natural;
98    /// use malachite_q::Rational;
99    ///
100    /// let (before_point, after_point) = Rational::from(3u32).digits(&Natural::from(10u32));
101    /// assert_eq!(before_point.to_debug_string(), "[3]");
102    /// assert_eq!(prefix_to_string(after_point, 10), "[]");
103    ///
104    /// let (before_point, after_point) =
105    ///     Rational::from_signeds(22, 7).digits(&Natural::from(10u32));
106    /// assert_eq!(before_point.to_debug_string(), "[3]");
107    /// assert_eq!(
108    ///     prefix_to_string(after_point, 10),
109    ///     "[1, 4, 2, 8, 5, 7, 1, 4, 2, 8, ...]"
110    /// );
111    /// ```
112    pub fn digits(&self, base: &Natural) -> (Vec<Natural>, RationalDigits) {
113        if let Some(log_base) = base.checked_log_base_2() {
114            let (before_point, after_point) = self.power_of_2_digits(log_base);
115            (before_point, RationalDigits::PowerOf2(after_point))
116        } else {
117            let mut remainder = self.abs();
118            let floor = (&remainder).floor().unsigned_abs();
119            remainder -= Self::from(&floor);
120            (
121                floor.to_digits_asc(base),
122                RationalDigits::General(RationalGeneralDigits {
123                    base: Self::from(base),
124                    remainder,
125                }),
126            )
127        }
128    }
129}
malachite_q/conversion/digits/digits.rs

malachite_q/conversion/digits/
digits.rs
