malachite_q/conversion/digits/to_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::to_power_of_2_digits::to_power_of_2_digits_helper;
11use alloc::collections::BTreeMap;
12use alloc::vec::Vec;
13use malachite_base::num::arithmetic::traits::{
14 Abs, AbsAssign, CheckedLogBase2, Floor, UnsignedAbs,
15};
16use malachite_base::num::conversion::traits::Digits;
17use malachite_base::rational_sequences::RationalSequence;
18use malachite_nz::natural::Natural;
19
20fn to_digits_helper(x: Rational, base: &Natural) -> (Vec<Natural>, RationalSequence<Natural>) {
21 if let Some(log_base) = base.checked_log_base_2() {
22 return to_power_of_2_digits_helper(x, log_base);
23 }
24 let floor = (&x).floor();
25 let mut remainder = x - Rational::from(&floor);
26 let before_point = floor.unsigned_abs().to_digits_asc(base);
27 let mut state_map = BTreeMap::new();
28 let mut digits = Vec::new();
29 let base = Rational::from(base);
30 for i in 0.. {
31 if remainder == 0u32 {
32 return (before_point, RationalSequence::from_vec(digits));
33 }
34 if let Some(previous_i) = state_map.insert(remainder.clone(), i) {
35 let repeating = digits.drain(previous_i..).collect();
36 return (before_point, RationalSequence::from_vecs(digits, repeating));
37 }
38 remainder *= &base;
39 let floor = (&remainder).floor().unsigned_abs();
40 digits.push(floor.clone());
41 remainder -= Rational::from(floor);
42 }
43 unreachable!()
44}
45
46impl Rational {
47 /// Returns the base-$b$ digits of a [`Rational`], taking the [`Rational`] by value.
48 ///
49 /// The output has two components. The first is a [`Vec`] of the digits of the integer portion
50 /// of the [`Rational`], least- to most-significant. The second is a [`RationalSequence`] of the
51 /// digits of the fractional portion.
52 ///
53 /// The output is in its simplest form: the integer-portion digits do not end with a zero, and
54 /// the fractional-portion digits do not end with infinitely many zeros or $(b-1)$s.
55 ///
56 /// The fractional portion may be very large; the length of the repeating part may be almost as
57 /// large as the denominator. If the [`Rational`] has a large denominator, consider using
58 /// [`digits`](Rational::digits) instead, which returns an iterator. That function computes the
59 /// fractional digits lazily and doesn't need to compute the entire repeating part.
60 ///
61 /// # Worst-case complexity
62 /// $T(n, m) = O(m2^n)$
63 ///
64 /// $M(n, m) = O(m2^n)$
65 ///
66 /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and $m$ is
67 /// `base.significant_bits()`.
68 ///
69 /// # Panics
70 /// Panics if `base` is less than 2.
71 ///
72 /// # Examples
73 /// ```
74 /// use malachite_base::strings::ToDebugString;
75 /// use malachite_nz::natural::Natural;
76 /// use malachite_q::Rational;
77 ///
78 /// let (before_point, after_point) = Rational::from(3u32).into_digits(&Natural::from(10u32));
79 /// assert_eq!(before_point.to_debug_string(), "[3]");
80 /// assert_eq!(after_point.to_string(), "[]");
81 ///
82 /// let (before_point, after_point) =
83 /// Rational::from_signeds(22, 7).into_digits(&Natural::from(10u32));
84 /// assert_eq!(before_point.to_debug_string(), "[3]");
85 /// assert_eq!(after_point.to_string(), "[[1, 4, 2, 8, 5, 7]]");
86 /// ```
87 #[inline]
88 pub fn into_digits(mut self, base: &Natural) -> (Vec<Natural>, RationalSequence<Natural>) {
89 self.abs_assign();
90 to_digits_helper(self, base)
91 }
92
93 /// Returns the base-$b$ digits of a [`Rational`], taking the [`Rational`] by reference.
94 ///
95 /// The output has two components. The first is a [`Vec`] of the digits of the integer portion
96 /// of the [`Rational`], least- to most-significant. The second is a [`RationalSequence`] of the
97 /// digits of the fractional portion.
98 ///
99 /// The output is in its simplest form: the integer-portion digits do not end with a zero, and
100 /// the fractional-portion digits do not end with infinitely many zeros or $(b-1)$s.
101 ///
102 /// The fractional portion may be very large; the length of the repeating part may be almost as
103 /// large as the denominator. If the [`Rational`] has a large denominator, consider using
104 /// [`digits`](Rational::digits) instead, which returns an iterator. That function computes the
105 /// fractional digits lazily and doesn't need to compute the entire repeating part.
106 ///
107 /// # Worst-case complexity
108 /// $T(n, m) = O(m2^n)$
109 ///
110 /// $M(n, m) = O(m2^n)$
111 ///
112 /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and $m$ is
113 /// `base.significant_bits()`.
114 ///
115 /// # Panics
116 /// Panics if `base` is less than 2.
117 ///
118 /// # Examples
119 /// ```
120 /// use malachite_base::strings::ToDebugString;
121 /// use malachite_nz::natural::Natural;
122 /// use malachite_q::Rational;
123 ///
124 /// let (before_point, after_point) = Rational::from(3u32).to_digits(&Natural::from(10u32));
125 /// assert_eq!(before_point.to_debug_string(), "[3]");
126 /// assert_eq!(after_point.to_string(), "[]");
127 ///
128 /// let (before_point, after_point) =
129 /// Rational::from_signeds(22, 7).to_digits(&Natural::from(10u32));
130 /// assert_eq!(before_point.to_debug_string(), "[3]");
131 /// assert_eq!(after_point.to_string(), "[[1, 4, 2, 8, 5, 7]]");
132 /// ```
133 pub fn to_digits(&self, base: &Natural) -> (Vec<Natural>, RationalSequence<Natural>) {
134 to_digits_helper(self.abs(), base)
135 }
136}